RT

常规思路，基环树找环，短边，跑树形DP

求大佬帮助

代码如下：

//树形DP 
//首先边数==点数说明这是一个基环树森林 
//不必慌张,在环上随意断开一条边,记相邻两点xx,yy,然后以xx/yy跑树形DP 
//然后答案加上强制不选xx/yy的最大值即可 
//特别地,如果是一个二元环,dfs是找不到的(会把他们当成父子忽略掉) 
//注意这只是环是二元的,这个基环树可不一定是二元的,开一个flag,判断一下,
//若是第一次找到父亲,说明是反向边,第二次则说明是二元环 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+10;
int n,xx,yy,e1,e2,siz,cnt=-1,head[maxn],w[maxn];
ll ans,f[maxn][2];
struct Node{int to,nex;} e[maxn<<1];
inline void add(int u,int to) {e[++cnt]=(Node){to,head[u]};head[u]=cnt;}
inline int gint() {
	char ch=getchar();int s=0,f=1;
	while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)) {s=(s<<3)+(s<<1)+(ch^48);ch=getchar();}
	return s*f;
}
inline void write(int x) {if(x/10) write(x/10);putchar((x%10)^48);}
bool vis[maxn],cut[maxn<<1];
bool flag[maxn];
inline void dfs(int u,int fa) {
	vis[u]=1;siz++;
	for(int i=head[u];i;i=e[i].nex) {
		int v=e[i].to;
		if(v==fa) {if(!flag[u]) {flag[u]=1;continue;}}
		if(vis[v]) {xx=u;yy=v;e1=i;e2=i^1;continue;}
		dfs(v,u);
	}
}
inline void DFS(int u,int fa) {
	f[u][0]=0;f[u][1]=w[u];
	for(int i=head[u];i;i=e[i].nex) {
		int v=e[i].to;if(v==fa||i==e1||i==e2) continue;
		DFS(v,u);
		f[u][0]+=max(f[v][0],f[v][1]);
		f[u][1]+=f[v][0];
	}
}
int main() {
	n=gint();
	for(int i=1,x;i<=n;i++) w[i]=gint(),x=gint(),add(i,x),add(x,i);
	for(int i=1;i<=n;i++) if(!vis[i]) {
		siz=0;ll tmp;
		dfs(i,-1);
		DFS(xx,-1);tmp=f[xx][0];
		DFS(yy,-1);ans+=max(tmp,f[yy][0]);
	}
	printf("%lld",ans);
	return 0;
}