不错的一道题目。
首先如果这是一棵树，那么本题就成了没有上司的舞会QAQ。。
加入一条边后唯一多的影响就是，这条边的两个端点不能同时选，其他条件是一样的。那么我们就删去这条边跑两次树形DP就行啦。。
一开始写的时候记录前驱节点。。然后发现找不到二元环QAQ。。
记录一下边就好了。。
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
#define N 1000005
using namespace std;
int cnt=1;
ll ans,f[N][2];
int n,root1,root2,v[N],head[N];
bool vis[N];
int list[N<<1],next[N<<1],flag[N<<1];
inline int read()
{
int a=0,f=1; char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1; c=getchar();}
while (c>='0'&&c<='9') {a=a*10+c-'0'; c=getchar();}
return a*f;
}
inline void insert(int x,int y)
{
next[++cnt]=head[x];
head[x]=cnt;
list[cnt]=y;
flag[cnt]=1;
}
void dfs(int x,int from)
{
vis[x]=1;
for (int i=head[x];i;i=next[i])
if (!vis[list[i]]) dfs(list[i],i);
else if ((from^1)!=i&&!root1)
root1=x,root2=list[i],flag[i]=flag[i^1]=0;
}
void dp(int x,int fa)
{
f[x][1]=v[x]; f[x][0]=0;
for (int i=head[x];i;i=next[i])
if (list[i]!=fa&&flag[i])
{
dp(list[i],x);
f[x][0]+=max(f[list[i]][0],f[list[i]][1]);
f[x][1]+=f[list[i]][0];
}
}
int main()
{
n=read();
for (int i=1;i<=n;i++)
{
v[i]=read();
int u=read();
insert(i,u); insert(u,i);
}
for (int i=1;i<=n;i++)
if (!vis[i])
{
root1=root2=0;
dfs(i,0);
dp(root1,0);
ll tmp=f[root1][0];
dp(root2,0);
tmp=max(tmp,f[root2][0]);
ans+=tmp;
}
cout << ans;
return 0;
}