题解：
早在寒假就讲了这题了，现在才A掉。话说如果题目上给出的关系就是一棵树的话，显然就是没有上司的舞会。但我们看样例就不是一棵树，而是成环的关系。不过也无妨，我们遇到环时同样可以解决，你在dfs找环的时候就可以记录一下任意两个在环上的点，然后把环断开，以这两个点为根分别跑树形dp。树形dp的状态定义也很明显：设dp[i][0/1]表示以i为根，选或不选它本身所获得的最大值。转移方程就呼之欲出了：dp[i][0]+=max(dp[son[i][1],dp[son[i]][0])。加上它的儿子选或不选的最大值。dp[i][1]+=dp[son[i]][0]。他选了他的儿子们都不能选。最后每个连通块内加上的都是dp[root][0]的最大值。
代码如下：
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+7; int n; int x,power[maxn]; struct node{ int nxt,to; }edge[maxn*2]; int cnt=1,head[maxn]; long long dp[maxn][2]; void add(int x,int y){ edge[++cnt].nxt=head[x]; edge[cnt].to=y; head[x]=cnt; } bool vis[maxn]; int edge_num,point_num1,point_num2; long long sum; void circle(int x,int f){ vis[x]=true; for(int i=head[x];i;i=edge[i].nxt){ int v=edge[i].to; if(v==f) continue; if(!vis[v]) circle(v,x); else{ edge_num=i; point_num1=x;//记录在环上两点的信息 point_num2=v; } } } void dfs(int x,int f){ dp[x][1]=power[x]; dp[x][0]=0; for(int i=head[x];i;i=edge[i].nxt){ int v=edge[i].to; if(v==f) continue; if(i==edge_num||i==(edge_num^1)) continue; dfs(v,x); dp[x][0]+=max(dp[v][0],dp[v][1]); dp[x][1]+=dp[v][0]; } } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d%d",&power[i],&x); add(i,x);add(x,i); } for(int i=1;i<=n;i++){ if(!vis[i]){ circle(i,0); dfs(point_num1,0); long long ans=dp[point_num1][0]; dfs(point_num2,0); sum+=max(ans,dp[point_num2][0]); } } printf("%lld\n",sum); return 0; }