先找环，然后对每个基环树上的点做一遍树形dp， 处理出这个点取或不取的dp值，让后枚举相邻两个点的取或不取状态，当成链来做

#include<bits/stdc++.h>
#define test() cout<<*******<<endl;
#define etr() cout<<endl;
using namespace std;
const int N=1e6+10;
int head[N],tot,w[N],vis[N];
struct node{
	int to,nxt;
};
node E[N<<1];
void addedge(int u,int v){
	tot++;
	E[tot].nxt=head[u];
	E[tot].to=v;
	head[u]=tot;
}
int n,is[N],fa[N],fir,sec;
void dfs(int u,int f){
	vis[u]=1;
	fa[u]=f;
	for(int i=head[u];i;i=E[i].nxt){
		int v=E[i].to;
		if(v==f) continue;
		if(vis[v]==2) continue;
		if(vis[v]){
			is[v]=1;
			fir=u;
			sec=v;
			int k=u;
			while(k!=v&&k!=0){
				is[k]=1;
				k=fa[k];
			}
			return;
		}
		else dfs(v,u);
	}
	vis[u]=2;
}
int dp[N][2];
void work(int u,int f){
	dp[u][0]=0;dp[u][1]=w[u];
	for(int i=head[u];i;i=E[i].nxt){
		int v=E[i].to;
		if(v==f||is[v]) continue;
		work(v,u);
		dp[u][0]=max(max(dp[v][1],dp[v][0]),dp[u][0]);
		dp[u][1]=max(dp[v][0]+w[u],dp[u][1]);
	}
}
int ans,f[N][2],a[N][2];
void getans(int u,int ff){
	for(int i=head[u];i;i=E[i].nxt){
		int v=E[i].to;
		if(v==ff||!is[v]) continue;
		if(v==fir) continue;
		f[u][0]=max(max(f[v][1],f[v][0]),f[u][0]);
		f[u][1]=max(f[v][0]+max(a[u][1],a[u][0]),f[u][1]);
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int x;cin>>w[i]>>x;
		addedge(i,x);
		addedge(x,i);
	}
	dfs(1,0);
	for(int i=1;i<=n;i++) cout<<is[i]<<" ";
	etr();
	for(int i=1;i<=n;i++){
		if(!dp[i][0]&&!dp[i][1]&&is[i]) work(i,0);
	}
	for(int i=1;i<=n;i++) cout<<dp[i][0]<<" "<<dp[i][1]<<endl;
	for(int i=1;i<=n;i++) a[i][0]=dp[i][0],a[i][1]=dp[i][1];
	a[sec][1]=-114514;
	a[fir][0]=-114514;
	getans(fir,0);
	ans=max(ans,f[fir][1]);
	a[sec][1]=dp[sec][1];
	a[fir][0]=dp[fir][0];
	a[fir][1]=-114514;
	a[sec][0]=-114514;
	getans(fir,0);
	ans=max(ans,f[fir][0]);
	a[sec][1]=-114514;
	a[fir][1]=-114514;
	a[fir][0]=dp[fir][0];
	a[sec][0]=dp[sec][0];
	getans(fir,0);
	ans=max(ans,f[fir][0]);
	cout<<ans<<endl;
	return 0;
}