最近小伙伴们省赛打得超级棒，4个队全是省一，还有陶神他们已经开赴成都参加区域赛，好羡慕啊。
第一次做树形DP，经历之前DP题目的磨练，觉得思路很简单
我首次尝试用MAP做，但是思路出了点问题，由于我之前是想对一个结构体数组进行维护，在结构体里面保存了老板的下属，但这样的话我就用的指针去访问数据，还用得蛮爽，直接用map映射结构体，这样的问题在dp的过程中出问题了，我没用dp数组进行维护，而是直接结构体里面保持量，这样的坏处是递归是加倍的，（因为0,1都要递归一遍）导致超时，我想采用记忆化搜索，不错，结果很正确，但是另一个问题是确定是否唯一就出问题了，由于记忆化搜索直接返回，导致无法判断底下是否唯一，结果是WA
其实我不要弄得那么复杂，map只是用来映射string 和 编号。用vector来存贮互属的关系。再用简单的dp数组来维护即可。引入uniq数组进行维护，以判断是否唯一，也是个状态的dp过程。
树形dp普遍是由叶子的最优值到根节点的最优值。
#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <map> #include <vector> using namespace std; map<string,int>mp; vector<int> v[210]; int dp[205][2]; int uniq[205][2]; void clean(int n) { mp.clear(); for (int i=0;i<=n;i++) v[i].clear(); memset(dp,0,sizeof dp); } void dfs(int x) { int r=v[x].size(); uniq[x][0]=uniq[x][1]=1; if (r==0) { dp[x][0]=0; dp[x][1]=1; return; } for (int i=0;i<r;i++){ int next=v[x][i]; dfs(next); dp[x][0]+=max(dp[next][0],dp[next][1]); dp[x][1]+=dp[next][0]; uniq[x][1]=uniq[next][0]; uniq[x][0]&=(dp[next][0]>dp[next][1])?uniq[next][0]:1; uniq[x][0]&=(dp[next][0]<dp[next][1])?uniq[next][1]:1; uniq[x][0]&=(dp[next][0]!=dp[next][1]); } dp[x][1]+=1; } int main() { int n; string str1,str2; while (scanf("%d",&n)) { int cnt=0; if (n==0) break; clean(n); cin>>str1; mp[str1]=cnt++; int i,j; for (i=1;i<n;i++) { cin>>str1>>str2; if (mp.find(str1)==mp.end()) mp[str1]=cnt++; if (mp.find(str2)==mp.end()) mp[str2]=cnt++; v[mp[str2]].push_back(mp[str1]); } bool istrue=true; dfs(0); int a0=dp[0][0]; int a1=dp[0][1]; int ans=max(a0,a1); if (a0>a1 && uniq[0][0]==0) istrue=false; else if (a0<a1 && uniq[0][1]==0) istrue=false; else if (a0==a1) istrue=false; if (istrue) printf("%d %s ",ans,"Yes"); else printf("%d %s ",ans,"No"); } return 0; }