0.序
假期上的qbxt图论班快忘干净了所以不得不重新学一遍
于是我就来写水题解了qwq
1.概述
说一下本题涉及的新东西：基环树。
基环树又叫做环套树，她和树的唯一区别就是基环树有(n)条边。
对于基环树(dp)的处理方式：
1.用各种奇奇怪怪的方法找到环；
2.把环断掉；
3.对断掉的两个端点分别(dp)。
具体套路参见洛谷P1453城市环路。
当然如果你对于此类(dp)不熟悉建议先做洛谷P1352没有上司的舞会。
2.细节
你以为完了？
请注意：此题并没有给出整个图连通的条件，所以，
这是一个基环树森林！
所以做多次(dp)就好了。
3.代码
注意#define int LL。
#define N 1000010
int n,pwr[N],fa[N],vis[N];
int r1,r2,ce,f[N][2];
struct Edge {
int to,nxt;
}e[N<<1];
int head[N],cnt=-1;
inline void ade(int u,int v){
e[++cnt].to=v;
e[cnt].nxt=head[u];
head[u]=cnt;
}
void Find(int now,int ff){
vis[now]=1;
for(int i=head[now];~i;i=e[i].nxt){
int v=e[i].to;
if(v!=ff){
if(vis[v]){
r1=now,r2=v,ce=i;
continue;
}
Find(v,now);
}
}
}
void DFS(int now,int ff){
f[now][0]=0,f[now][1]=pwr[now];
for(int i=head[now];~i;i=e[i].nxt){
int v=e[i].to;
if(v!=ff&&i!=ce&&(i^1)!=ce){
DFS(v,now);
f[now][1]+=f[v][0];
f[now][0]+=max(f[v][0],f[v][1]);
}
}
}
signed main(){
memset(head,-1,sizeof(head));
Read(n);
for(int i=1;i<=n;i++){
Read(pwr[i]),Read(fa[i]);
ade(fa[i],i),ade(i,fa[i]);
}
int ans=0,tmp;
for(int i=1;i<=n;i++){
if(!vis[i]){
Find(i,-2);
DFS(r1,-1);
tmp=f[r1][0];
DFS(r2,-1);
tmp=max(tmp,f[r2][0]);
ans+=tmp;
}
}
cout<<ans<<endl;
return 0;
}