首先这是一个有$n$个点$n$条边的图（据大佬们说这玩意儿叫做基环树？）
不难（完全没有）发现每个连通块里最多只有一个环
那么找到这个环，然后把它断开，再对它的两个端点分别跑树形dp
设$dp[u][0]$表示该点不选，$dp[u][1]$表示选，然后跑一个没有上司的舞会就可以了
1 //minamoto 2 #include<bits/stdc++.h> 3 #define ll long long 4 using namespace std; 5 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 6 char buf[1<<21],*p1=buf,*p2=buf; 7 template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;} 8 inline int read(){ 9 #define num ch-'0' 10 char ch;bool flag=0;int res; 11 while(!isdigit(ch=getc())) 12 (ch=='-')&&(flag=true); 13 for(res=num;isdigit(ch=getc());res=res*10+num); 14 (flag)&&(res=-res); 15 #undef num 16 return res; 17 } 18 const int N=1e6+5; 19 int head[N],Next[N<<1],ver[N<<1],tot=1; 20 inline void add(int u,int v){ 21 ver[++tot]=v,Next[tot]=head[u],head[u]=tot; 22 } 23 int vis[N],val[N],n,x1,x2,E;ll dp[N][2],ans=0; 24 void find(int u,int l){ 25 vis[u]=1; 26 for(int i=head[u];i;i=Next[i]){ 27 if((i^1)==l) continue; 28 if(vis[ver[i]]){ 29 x1=u,x2=ver[i],E=i;continue; 30 }find(ver[i],i); 31 } 32 } 33 void dfs(int u,int l){ 34 dp[u][0]=0,dp[u][1]=val[u]; 35 for(int i=head[u];i;i=Next[i]){ 36 if((i^1)==l) continue; 37 if(i==E||(i^1)==E) continue; 38 dfs(ver[i],i); 39 dp[u][1]+=dp[ver[i]][0],dp[u][0]+=max(dp[ver[i]][0],dp[ver[i]][1]); 40 } 41 } 42 int main(){ 43 // freopen("testdata.in","r",stdin); 44 n=read(); 45 for(int i=1,v;i<=n;++i) 46 val[i]=read(),v=read(),add(i,v),add(v,i); 47 for(int i=1;i<=n;++i){ 48 if(vis[i]) continue; 49 find(i,0),dfs(x1,0); 50 ll res=dp[x1][0]; 51 dfs(x2,0); 52 cmax(res,dp[x2][0]); 53 ans+=res; 54 } 55 printf("%lld ",ans); 56 return 0; 57 }