题目大意：给定一个 N 个点的外向树森林，点有点权。从该树中选出若干顶点组成一个集合，满足任意相邻的两个顶点不同时出现在该集合中，求这样集合中点权和的最大值为多少。

题解：与树相比，该题多了环这个结构。对于环上任意一条边来说，边的端点不可能同时被选取，因此，可以选择环上任意一条边，将其断开，答案不变。这样就将环的问题转化成了树的问题，接着，分别以断开边的端点为根，做两次树形 dp，将两个不选根节点的权值最大值取最大加入答案贡献即可。

另外，需要注意的是，相比较有向图找环，无向图由于边的双向性，仅仅用 vis[u]=1 进行判断会挂掉，因此，需要记录下前一条边，并保证后一条边不等于前一条边才行。这里不选点是因为两个点组成的环的情况。

另外，用并查集进行找环也是可以的。

代码如下

#include <bits/stdc++.h>

using namespace std;

const int maxn=1e6+10;

inline int read(){

	int x=0,f=1;char ch;

	do{ch=getchar();if(ch=='-')f=-1;}while(!isdigit(ch));

	do{x=x*10+ch-'0';ch=getchar();}while(isdigit(ch));

	return f*x;

}

struct node{

	int nxt,to;

}e[maxn<<1];

int tot=1,head[maxn];

inline void add_edge(int from,int to){

	e[++tot]=node{head[from],to},head[from]=tot;

}

int n,a,b,edge,val[maxn],vis[maxn];

long long ans,dp[maxn][2];

void read_and_parse(){

	n=read();

	for(int i=1,to;i<=n;i++)val[i]=read(),to=read(),add_edge(i,to),add_edge(to,i);

}

void find(int u,int pre){

	vis[u]=1;

	for(int i=head[u];i;i=e[i].nxt){

		int v=e[i].to;if(i==(pre^1))continue;

		if(!vis[v])find(v,i);

		else if(vis[v]==1)a=u,b=v,edge=i;

	}

	vis[u]=2;

}

void dfs(int u,int fa){

	dp[u][1]=val[u],dp[u][0]=0;

	for(int i=head[u];i;i=e[i].nxt){

		int v=e[i].to;

		if(v==fa||i==edge||i==(edge^1))continue;

		dfs(v,u);

		dp[u][1]+=dp[v][0];

		dp[u][0]+=max(dp[v][0],dp[v][1]);

	}

}

void solve(){

	for(int i=1;i<=n;i++)if(!vis[i]){

		find(i,-1);

		dfs(a,0);

		long long res1=dp[a][0];

		dfs(b,0);

		long long res2=dp[b][0];

		ans+=max(res1,res2);

	}

	printf("%lld\n",ans);

}

int main(){

	read_and_parse();

	solve();

	return 0;

}