```
#include<bits/stdc++.h>
#define maxn 1000005
#define ll long long
using namespace std;
struct edge{
int nxt,to;
} e[maxn<<1];
bool vis[maxn];
int head[maxn],cnt=1,n;
int val[maxn],ringpt,ringpt2,not_pass;
ll dp[2][maxn];
void add(int u,int v)
{
e[++cnt].nxt=head[u];e[cnt].to=v;head[u]=cnt;
}
void getdp(int rt,int fa)
{
dp[0][rt]=0;dp[1][rt]=val[rt];
for(int i=head[rt];i;i=e[i].nxt){
if(e[i].to==fa) continue;
if(rt==ringpt&&e[i].to==ringpt2) continue;
if(rt==ringpt2&&e[i].to==ringpt) continue;
getdp(e[i].to,rt);
dp[0][rt]+=max(dp[0][e[i].to],dp[1][e[i].to]);
dp[1][rt]+=dp[0][e[i].to];
}
}
void dfs(int rt,int fa)
{
vis[rt]=1;
for(int i=head[rt];i;i=e[i].nxt){
if(e[i].to==fa) continue;
if(!vis[e[i].to]) dfs(e[i].to,rt);
else{
not_pass=i;
ringpt=e[i].to,ringpt2=rt;
}
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++){
int y;scanf("%d%d",&val[i],&y);
add(i,y);add(y,i);
}
ll ans=0;
for(int i=1;i<=n;i++){
if(vis[i]) continue;
dfs(i,-1);
getdp(ringpt,-1);
long long tmp=dp[0][ringpt];
getdp(ringpt2,-1);
ans+=max(tmp,dp[0][ringpt2]);
}
cout<<ans<<endl;
}
```
by SGOI_Aromyase @ 2018-04-16 17:11:52
因为有可能两个人互相讨厌。
by ErkkiErkko @ 2018-06-04 17:29:35