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)

    link : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem& ...

  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][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 ...

  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

    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 built-in services for ...

  8. JavaNIO buffer

    package com.nio.test; import java.nio.ByteBuffer; import org.junit.Test; /** * * @author fliay * * One ...

  9. 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 ...

  10. 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 ...