题解：
早在寒假就讲了这题了，现在才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;
}