Loading... [题目链接](https://www.luogu.org/problemnew/show/P1271 "题目链接") <!--more--> * * * * 树上dp * 水题，和《没有上司的舞会》基本一样，多个字符串的hash（可以直接用STL-map） * 设计状态：f\[i\]\[0/1\]表示第i个节点参加活动（1）或者不参加活动（0）。 * 状态转移方程： 1. $f\[fa\]\[1\]+=f\[x\]\[0\]$ 2. $f\[fa\]\[0\]+=max(f\[x\]\[0\],f\[x\]\[1\])$ * * * #### 代码如下 ```cpp #include<bits/stdc++.h> using namespace std; map<string,int> hash; vector<int> son[209]; struct Edge{ string u,fa; int w; }edge[209]; int n,f[209][2],tot,tot_h,val[209],head[209]; void dp(int x,int fa){ f[x][0]=0; f[x][1]=val[x]; for(int i=0;i<son[x].size();i++){ int y=son[x][i]; if(y==fa) continue; dp(y,x); f[x][1]+=f[y][0]; f[x][0]+=max(f[y][0],f[y][1]); } } int main(){ cin>>n; int s; for(int i=1;i<=n;i++){ cin>>edge[i].u>>val[i]>>edge[i].fa; hash[edge[i].u]=i; } for(int i=1;i<=n;i++){ son[hash[edge[i].fa]].push_back(i); } for(int i=1;i<=n;i++){ if(!hash[edge[i].u]) s=i; } dp(s,-1); cout<<max(f[s][1],f[s][0]); return 0; } ``` Last modification：March 14, 2020 © Allow specification reprint Like 如果觉得我的文章对你有用，请随意赞赏