本文主要是介绍UVA - 1220 Party at Hali-Bula（树形dp），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目地址点击打开链接；
开始以为是各种dfs爆搜yy中。。。；
不想完全看题解，搞了很久，看了一眼后缀，据说是树形dp；
然后顿悟开始修改；随他去吧；
用一个二维dp【a】【b】 来更新最大值，a表示这个节点的编号，b有两个值，0,1表示这个点取与不取；
用一个vector来建树；从根节点开始，也就是big boss，向他的员工出发dfs，每个点可以取，也可以不取，
取：该点的所有子结点都不可取；
不取：该点的所有子节点中寻找取与不取的最大值来更新；
当到达叶子时，叶子一定是取的（max）并且dp【a】【1】值为1，因为只有这一个人；
然后就得到最大值了；
差一点gg的是，他要求你判断max的方案是否唯一，我傻，没办法，于是再来一个dfs来开始判断
取：从子节点不取中判断；
不取： 如果子节点的取和不取的值相同的话，那说明一点方案不唯一，（因为当初取的时候就是存的取和不取中的最大值，如果两者相等，则说明重复）
#include <iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdio>
#include<map>
#include<vector>using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=200+5;
map<string,int>mp;
int n;
int vis[maxn];
vector<int> eg[maxn];
int flag;
int nn;
int ans;
int dp[maxn][3];
void dfs(int a,int ok)
{if(eg[a].size()==0&&ok){dp[a][1]=1;dp[a][0]=0;}if(vis[a])return;if(ok){dp[a][1]=1;for(int i=0;i<eg[a].size();i++){ vis[a]=1;dfs(eg[a][i],0);dp[a][1]+=dp[eg[a][i]][0];}}dp[a][0]=0;for(int i=0;i<eg[a].size();i++){dfs(eg[a][i],1);dp[a][0]+=max(dp[eg[a][i]][1],dp[eg[a][i]][0]);}if(dp[a][0]==dp[a][1])flag=1;
}
int oj(int a,int ok)
{if(ok){for(int i=0;i<eg[a].size();i++)if(oj(eg[a][i],0))return 1;}else{for(int i=0;i<eg[a].size();i++){if(dp[eg[a][i]][0]==dp[eg[a][i]][1])return 1;}}return 0;
}
int main()
{string a,b;while(cin>>n&&n){cin>>a;int num=1;mp.clear();for(int i=0;i<=n;i++)eg[i].clear();mp[a]=num;for(int i=0;i<n-1;i++){cin>>a>>b;if(!mp[a]){num++;mp[a]=num;}if(!mp[b]){num++;mp[b]=num;}eg[mp[b]].push_back(mp[a]);}nn=0;ans=0;flag=0;memset(vis,0,sizeof(vis));memset(dp,0,sizeof(dp));dfs(1,1);ans=max(dp[1][0],dp[1][1]);if(dp[1][0]==dp[1][1])flag=1;else{if(dp[1][0]>dp[1][1])flag=oj(1,0);elseflag=oj(1,1);}cout<<ans<<" ";if(flag)cout<<"No"<<endl;elsecout<<"Yes"<<endl;}return 0;
}
唉，太菜了 了 了了了了了了了了了，继续努力啊！！！
不过还好，以后一定要坚持，觉得如果自己不看题解也可以做出来的题那么，你就不要看题解！
这篇关于UVA - 1220 Party at Hali-Bula（树形dp）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
