具体思路

$n$ 个点 $n$ 条边显然是基环树。

我们先考虑普通的树形 dp。

设 $f_{x,0/1}$ 表示以 $x$ 为根的子树内， $x$ 节点不选或选的最大战斗力总和。

$$f_{x,0}=\sum \max \limits_{y \in son_x} \{f_{y,0},f_{y,1} \} $$$$f_{x,1}=\sum_{y \in son_x}f_{y,0}$$

即 $x$ 不选的话，$x$ 的儿子选或不选都行，$x$ 选的话，$x$ 的儿子都不能选。

考虑环的影响。

设环的两个端点分别为 $x,y$。

• $edge(x,y)$ 无影响：
  1. $x$ 选，$y$ 不选。
  2. $x$ 不选，$y$ 选或不选。
• $edge(x,y)$ 有影响：
  1. $x$ 选，$y$ 选。

对于 $x,y$ 同时选的情况，我们需要强制 $x$ 不选或 $y$ 不选。

即跑一遍以 $x$ 为根的树形 dp，跑一遍以 $y$ 为根的树形 dp。

$$ans=\max \{ f_{x,0},f_{y,0} \}$$

注意：

• 不保证连通，有可能是基环树森林。
• 要建无向边，有向边的话你从另一个端点出发就走不了了。
• 可以用并查集维护连通性来求出每个基环树森林环的两个端点。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int>PII;
const int N=1e6+5;
struct edge{
	int x,y,pre;
}a[2*N];
int last[N],alen;
void ins(int x,int y){
	a[++alen]=edge{x,y,last[x]};
	last[x]=alen;
}
int fa[N];
int get(int x){
	if(fa[x]==x)return x;
	return fa[x]=get(fa[x]);
}
vector<PII>root;
int w[N];LL f[N][2];
void treedp(int x,int fa){
	f[x][0]=0,f[x][1]=w[x];
	for(int k=last[x];k;k=a[k].pre){
		int y=a[k].y;
		if(y==fa)continue;
		treedp(y,x);
		f[x][0]+=max(f[y][0],f[y][1]);
		f[x][1]+=f[y][0];
	}
}
int main(){
	int n;scanf("%d",&n);
	alen=1;memset(last,0,sizeof(last));
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
	for(int x=1;x<=n;x++){
		int y;scanf("%d%d",&w[x],&y);
		int tx=get(x),ty=get(y);
		if(tx==ty){
			root.push_back({x,y});
		}
		else{
			fa[tx]=ty;
			ins(x,y),ins(y,x);
		}
	}
	LL ans=0;
	for(auto i:root){
		int x=i.first,y=i.second;
		LL res=0;
		treedp(x,0);
		res=max(res,f[x][0]);
		treedp(y,0);
		res=max(res,f[y][0]);
		ans=ans+res;
	}
	printf("%lld",ans);
	return 0;
}