The question ：

There is a tree. , Select as many nodes as possible, so that the two nodes are not adjacent , That is, each node and its children can only choose one . Find the maximum number of nodes in accordance with the scheme , And judge whether the optimal scheme is unique .

analysis ：

d(u, 0) Said to u In the subtree of the root , No election u The maximum number of people a node can get ,f(u, 0) Indicates whether the solution is unique .

d(u, 1) Express election u The maximum number of people a node can get , Empathy ,f(u, 1) Indicates whether the solution is unique .

The transfer of state ：

• d(u, 1) The calculation of ： Because chose u node , therefore u You can't select any child nodes of .d(u, 1) = sum{ d(v, 0) | v yes u Child nodes of }
• f(u, 1) The calculation of ： If and only if f(v, 0) == 1 when ,f(u, 1) It's just 1
• d(u, 0) The calculation of ： Because there is no choice u node , So for each child node v No choice .d(u, 0) = sum{ max(d(v, 0),  d(v, 1)) }
• f(u, 0) The calculation of ： There are not only two scenarios , Some d(v, 1) == d(v, 0) perhaps Corresponding to max Of the plan f by 1

This is used here. C++ Medium map, Match the string to the number , It's easy to write code .

``` //#define LOCAL
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <vector>
#include <iostream>
using namespace std;

const int maxn = ;
vector<int> sons[maxn];
map<string, int> dict;
int cnt, d[maxn][], f[maxn][];

int ID(const string& s)
{
if(!dict.count(s))    dict[s] = cnt++;
return dict[s];
}

int dp(int u, int k) {
f[u][k] = ;
d[u][k] = k;
for(int i = ; i < sons[u].size(); i++) {
int v = sons[u][i];
if(k == ) {  // Select node u
d[u][] += dp(v, );
if(!f[v][]) f[u][] = ; // If the child node v Is not the only , Then the parent node u It's not the only one
} else {
d[u][] += max(dp(v, ), dp(v, ));
if(d[v][] == d[v][]) f[u][k] = ;
else if(d[v][] > d[v][] && !f[v][]) f[u][k] = ;
else if(d[v][] > d[v][] && !f[v][]) f[u][k] = ;
}
}
return d[u][k];
}

int main(void)
{
#ifdef    LOCAL
freopen("1220in.txt", "r", stdin);
#endif

int n;
string s, s2;
while(cin >> n >> s)
{
getchar();
cnt = ;
dict.clear();
for(int i = ; i <= n; ++i)    sons[i].clear();

//cin >> s;
ID(s);
for(int i = ; i < n; ++i)
{
cin >> s >> s2;
sons[ID(s2)].push_back(ID(s));
}
printf("%d ", max(dp(, ), dp(, )) );
bool unique = false;
if(d[][] > d[][] && f[][])    unique = true;
if(d[][] > d[][] && f[][])    unique = true;
printf("%s\n", unique ? "Yes" : "No");
}

return ;
}```

Code King

## UVa 1220 ( The largest independent set of trees ) Party at Hali-Bula More articles about

1. UVa 1220 Hali-Bula My party （ The largest independent set of trees ）

https://vjudge.net/problem/UVA-1220 The question : There are... In the company n Individuals form a tree structure , That is, except for the boss, every employee has a unique direct supervisor . Ask for as many people as possible , But you can't choose one person and his straight line at the same time ...

2. POJ 3342 Party at Hali-Bula / HDU 2412 Party at Hali-Bula / UVAlive 3794 Party at Hali-Bula / UVA 1220 Party at Hali-Bula（ Tree dynamic planning ）

POJ 3342 Party at Hali-Bula / HDU 2412 Party at Hali-Bula / UVAlive 3794 Party at Hali-Bula / UVA 12 ...

3. UVa 1220 - Party at Hali-Bula（ Tree form DP）

4. POJ 2342 The largest independent set of trees

The question : Based on the maximum independent set of trees , Add the weight . Ask for the biggest . analysis : Use the way to write the memory of the brush table , Consider a click and no select , Return mode pair type . First , Rootless trees turn to rooted trees ,dp(root). Pay attention to is :u No election , So his son's Day ...

5. POJ 3342 Party at Hali-Bula ( Tree form dp The largest independent set of trees Judge many solutions Good question )

Party at Hali-Bula Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 5660   Accepted: 202 ...

6. Find the maximum independent set of a tree , Minimum point coverage , The minimum dominating set greedy and Tree form dp

Catalog Find the maximum independent set of a tree , Minimum point coverage , The minimum dominating set Three definitions Greedy solution Tree form DP solution ( If you have any questions, please leave a message or chat && Welcome to exchange and discuss Find the maximum independent set of a tree , Minimum point coverage , The minimum dominating set Three definitions Maximum ...

7. HDU - 1520 Anniversary party （ The largest independent set of trees ）

Time limit :1000 ms :Memory limit :32768 kB: OS :Windows There is going to be a party to celebrate t ...

8. UVA - 1220 Party at Hali-Bula The largest independent set of trees

The question :  Given n personal , There is a superior subordinate relationship , Everyone has only one superior , Find the maximum independent set . And judge whether the maximum independent set is unique Ideas :d[i] Said to i In the subtree of the root , No choice i The largest independent set of nodes ,f[i] Said to i The son of the root ...

9. UVa 1220 Party at Hali-Bula （ Tree form DP, The largest independent set ）

The question : Company has n Individuals form a tree structure , Except for the boss, they all have a direct supervisor , Ask for as many people as possible , But you can't choose one person and his immediate superior at the same time , How many people can I choose at most , And it's not the only solution . Analysis : This problem is almost the largest independent set of trees ...

## Random recommendation

1. ng-bind And ng-model difference

Two way binding , Generally speaking, it's like this <input ng-model="object.xxx"> <span ng-bind="object.xxx"&g ...

2. Repair happens “ Because of data mobility , Failed to continue with NOLOCK Mode scan ” Wrong database

Recently, an error was found in the system operation , The error message is as follows : error message : Inquire about A201412C20568 Document information error ---> System.Data.OleDb.OleDbException: Because of data mobility , ...

3. C# Design patterns (5)—— Builder pattern （Builder Pattern）

One . introduction In software system , Sometimes you need to create a complex object , And this complex object is composed of its sub objects through certain steps . For example, in a purchasing system , If you need a buyer to buy a batch of computers , In this practical need , A computer is a complex object , ...

4. Spark Official documents —— Write and run locally scala Program

Quick start How will this be used scala.java.python Write a spark Click the program in mode . First of all, you only need to build successfully on one machine Spark: practice : Get into Spark Root directory , Enter the command :\$ sbt/sbt ...

5. Counting - SGU 117（ Fast power ）

The main idea of the topic : Ask below N How many numbers are there in the number M Power can divide K The code is as follows : ======================================================== #include&l ...

6. jq Medium ajax

jq Yes ajax It was packaged , stay jq in \$.ajax() Method is the lowest level method , The second level is load() , get() , post() Method , The third layer is \$.getScript() and \$.getJSON(). Basically the second ...

7. Hive Basics （4）---Hive Built in services for