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 HaliBula More articles about
 UVa 1220 HaliBula My party （ The largest independent set of trees ）
https://vjudge.net/problem/UVA1220 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 ...
 POJ 3342 Party at HaliBula / HDU 2412 Party at HaliBula / UVAlive 3794 Party at HaliBula / UVA 1220 Party at HaliBula（ Tree dynamic planning ）
POJ 3342 Party at HaliBula / HDU 2412 Party at HaliBula / UVAlive 3794 Party at HaliBula / UVA 12 ...
 UVa 1220  Party at HaliBula（ Tree form DP）
link : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem& ...
 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 ...
 POJ 3342 Party at HaliBula ( Tree form dp The largest independent set of trees Judge many solutions Good question )
Party at HaliBula Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 5660 Accepted: 202 ...
 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 ...
 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 ...
 UVA  1220 Party at HaliBula 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][0] Said to i In the subtree of the root , No choice i The largest independent set of nodes ,f[i][0] Said to i The son of the root ...
 UVa 1220 Party at HaliBula （ 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
 ngbind And ngmodel difference
Two way binding , Generally speaking, it's like this <input ngmodel="object.xxx"> <span ngbind="object.xxx"&g ...
 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 , ...
 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 , ...
 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 ...
 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 ...
 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 ...
 Hive Basics （4）Hive Built in services for
Copyright notice :<—— This article is dedicated to the creation of , If you want to reprint , Please indicate the source @http://blog.csdn.net/gamer_gyt <—— Catalog (?)[+] One :Hive Several builtin services for ...
 JavaNIO buffer
package com.nio.test; import java.nio.ByteBuffer; import org.junit.Test; /** * * @author fliay * * One ...
 VINS Check the parallax of the estimator
Why check the parallax VINS In order to control the amount of optimization calculation , In real time , Only some frames before the current frame are optimized , Not the whole history frame . The number of locally optimized frames is the window size . To maintain the window size , You need to remove old frames and add new ones , That's marginalization ...
 Ten minutes through NPM Create a command line tool
The festival holiday , Do you want to write some code ? Take ten minutes and learn how to do it NPM Build a command line tool . I wrote a little demo, Used to replace touch The create file command touchme , You can create your own “ The Buddha bless ” Annotated file ...