题目大意：给定一个 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;
}