将仇恨关系连边后，这张图实际上就是一张基环树森林，对于一颗树显然可以十分容易的dp，那么先对于基环树上的某一棵生成树dp两次，分别令那条非树边的两端中的某一个点不能选，另一个点随意，两次取max即答案
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 1000005 4 struct ji{ 5 int nex,to; 6 }edge[N<<1]; 7 int E,n,x,y,head[N],a[N],vis[N]; 8 long long s,ans,f[N][2]; 9 void add(int x,int y){ 10 edge[E].nex=head[x]; 11 edge[E].to=y; 12 head[x]=E++; 13 } 14 void dfs(int k,int fa){ 15 vis[k]=1; 16 for(int i=head[k];i!=-1;i=edge[i].nex) 17 if (edge[i].to!=fa) 18 if (!vis[edge[i].to])dfs(edge[i].to,k); 19 else{ 20 x=k; 21 y=edge[i].to; 22 edge[i].to=fa; 23 } 24 } 25 void dp(int k,int fa,int x){ 26 f[k][0]=f[k][1]=0; 27 for(int i=head[k];i!=-1;i=edge[i].nex) 28 if (edge[i].to!=fa){ 29 dp(edge[i].to,k,x); 30 f[k][0]+=max(f[edge[i].to][0],f[edge[i].to][1]); 31 f[k][1]+=f[edge[i].to][0]; 32 } 33 if (k!=x)f[k][1]+=a[k]; 34 else f[k][1]=0; 35 } 36 int main(){ 37 scanf("%d",&n); 38 memset(head,-1,sizeof(head)); 39 for(int i=1;i<=n;i++){ 40 scanf("%d%d",&a[i],&x); 41 add(i,x); 42 add(x,i); 43 } 44 for(int i=1;i<=n;i++) 45 if (!vis[i]){ 46 dfs(i,0); 47 dp(i,0,x); 48 s=max(f[i][0],f[i][1]); 49 dp(i,0,y); 50 ans+=max(s,max(f[i][0],f[i][1])); 51 } 52 printf("%lld",ans); 53 }