对于一个联通块内，有且只有一个环，即n个点n条边
那么找到那个环，然后任意断一条边，这个联通块就变成一棵树了，然后做树形DP就行了
对于断的边要记录下来DP时特判
Code
#include#include #include #define ll long long#define N 1000010using namespace std;struct info{int to,nex;}e[N*2];int n,A[N],tot=1,head[N],x,y,ee;ll Ans,dp[N][2];bool vis[N];void Link(int u,int v){ e[++tot].nex=head[u];head[u]=tot;e[tot].to=v;}inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}bool Fvis[N];void Find(int u,int fa){ Fvis[u]=1; for(int i=head[u],v;i;i=e[i].nex){ if((v=e[i].to)==fa) continue; if(Fvis[v]) x=u,y=v,ee=i; else Find(v,u); }}void DP(int u,int fa){ vis[u]=1; dp[u][0]=0,dp[u][1]=A[u]; for(int i=head[u],v;i;i=e[i].nex){ if((v=e[i].to)!=fa&&i!=ee&&(i^1)!=ee){ DP(v,u); dp[u][1]+=dp[v][0]; dp[u][0]+=max(dp[v][0],dp[v][1]); } }}void solve(int u){ if(vis[u]) return; vis[u]=1; memset(Fvis,0,sizeof(Fvis)); Find(u,0); DP(x,0); ll t=dp[x][0]; DP(y,0); Ans+=max(t,dp[y][0]);}int main(){ n=read(); for(int i=1,x;i<=n;++i) A[i]=read(),Link(x=read(),i),Link(i,x); for(int i=1;i<=n;solve(i++)); printf("%lld\n",Ans); return 0;}