AC了
完整代码
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct edge{
int next;
int to;
};
edge a[2000100];
int n,m,u,v,i,j,head[1000100];
long long w[1000100],dp[1000100][2],dp2[1000100][2],ans,cnt;
bool book[1000100],book2[1000100],vis[1000100];
inline void add(int u,int v){
a[cnt]=(edge){head[u],v};
head[u]=cnt;
cnt++;
}
inline int read(){
int s=0;
char ch=getchar();
while(ch<='0'||ch>'9'){ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s;
}
void dpdfs(int x){
book[x]=true;
dp[x][1]=w[x];
for(register int i=head[x];i+1;i=a[i].next){
int y=a[i].to;
if(y==-1||book[y])
continue;
dpdfs(y);
dp[x][1]+=dp[y][0];
dp[x][0]+=max(dp[y][0],dp[y][1]);
}
}
void dpdfs2(int x){
book2[x]=true;
dp2[x][1]=w[x];
for(register int i=head[x];i+1;i=a[i].next){
int y=a[i].to;
if(y==-1||book2[y])
continue;
dpdfs2(y);
dp2[x][1]+=dp2[y][0];
dp2[x][0]+=max(dp2[y][0],dp2[y][1]);
}
}
void dfs(int x,int pre){
vis[x]=true;
for(register int i=head[x];i+1;i=a[i].next){
int y=a[i].to;
if(y==pre||y==-1)
continue;
if(vis[y]){
u=x;v=y;
//cout<<a[i].to<<" "<<a[i^1].to<<endl;
a[i].to=-1;
a[i^1].to=-1;
continue;
}
dfs(y,x);
}
}
int main(){
scanf("%d",&n);
for(register int i=1;i<=n;i++)
head[i]=-1;
for(register int i=1;i<=n;i++){
w[i]=read();
u=read();
add(u,i);
add(i,u);
}
for(register int i=1;i<=n;i++){
if(vis[i])
continue;
u=v=0;
dfs(i,0);
dpdfs(u);
dpdfs2(v);
ans+=max(dp[u][0],dp2[v][0]);
}
printf("%lld",ans);
return 0;
}
```
by Cobalt @ 2018-08-14 17:24:14