Description
Z国的骑士团是一个很有*的组织，帮会中汇聚了来自各地的精英。他们劫富济贫，惩恶扬善，受到社会各
界的赞扬。最近发生了一件可怕的事情，邪恶的Y国发动了一场针对Z国的侵略战争。战火绵延五百里，在和平环境
中安逸了数百年的Z国又怎能抵挡的住Y国的军队。于是人们把所有的希望都寄托在了骑士团的身上，就像期待有一
个真龙天子的降生，带领正义打败邪恶。骑士团是肯定具有打败邪恶*的能力的，但是骑士们互相之间往往有一
些矛盾。每个骑士都有且仅有一个自己最厌恶的骑士（当然不是他自己），他是绝对不会与自己最厌恶的人一同出
征的。战火绵延，人民生灵涂炭，组织起一个骑士军团加入战斗刻不容缓！国王交给了你一个艰巨的任务，从所有
的骑士中选出一个骑士军团，使得军团内没有矛盾的两人（不存在一个骑士与他最痛恨的人一同被选入骑士军团的
情况），并且，使得这支骑士军团最具有战斗力。为了描述战斗力，我们将骑士按照1至N编号，给每名骑士一个战
斗力的估计，一个军团的战斗力为所有骑士的战斗力总和。
Input
第一行包含一个正整数N，描述骑士团的人数。接下来N行，每行两个正整数，按顺序描述每一名骑士的战斗力
和他最痛恨的骑士。
Output
应包含一行，包含一个整数，表示你所选出的骑士军团的战斗力。
Sample Input
10 2
20 3
30 1
Sample Output
HINT
N ≤ 1 000 000，每名骑士的战斗力都是不大于 1 000 000的正整数。
正解：基环外向树+DP
解题报告：
这道题的模型就是基环外向树，n个点，n条边，显然题目中给的实际上是无向边，在有重边的情况下将会成为一棵树，否则就会成为一个环，显然是若干个连通块。
那么每个连通块可以用同样的方法处理：对于树，直接一遍树形DP即可。对于环，我们找到产生环的那条边，考虑这条边连接的两个结点，我们可以删掉这条边然后对于这条边的两个顶点u和v，第一次以u为根，做一遍树形DP，得到不取u的最大值；第二次以v为根，同样做法，两者取一个max，注意这条边必须要删掉，然而我想了点奇奇怪怪的方法才删掉的，因为有重边不是很好判...
最后把每个连通块的答案加起来就可以了。
//It is made by jump~
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
typedef long long LL;
#define RG register
const int inf = (<<);
const int MAXN = ;
const int MAXM = ;
int n,ecnt,val[MAXN],root,root2;
int first[MAXN],to[MAXM],next[MAXM];
bool vis[MAXN];
LL f[MAXN][];
int dui[MAXN],deep[MAXN],head,tail,father[MAXN],use[MAXN],uu;
LL ans; inline int getint()
{
RG int w=,q=; RG char c=getchar();
while((c<'' || c>'') && c!='-') c=getchar(); if(c=='-') q=,c=getchar();
while (c>='' && c<='') w=w*+c-'', c=getchar(); return q ? -w : w;
} inline void dp(RG int x,RG int fa){
f[x][]=f[x][]=; use[x]=uu;
for(RG int i=first[x];i;i=next[i]) {
RG int v=to[i]; if(v==fa) continue;
if((x==root && v==root2) || (x==root2 && v==root)) continue;//强行删掉这条边
if(use[v]==uu) continue;
dp(v,x); f[x][]+=max(f[v][],f[v][]); f[x][]+=f[v][];
}
f[x][]+=val[x];
} inline void find(RG int x){
head=tail=; dui[++tail]=x; RG int u;RG LL maxl=;
RG bool ok=false;
while(head<tail) {
head++; u=dui[head]; vis[u]=;
for(RG int i=first[u];i;i=next[i]) {
RG int v=to[i]; if(v==father[u]) continue;
if(deep[v]<deep[u] && deep[v]!=) {
root=u; root2=v; uu++; dp(v,); maxl=max(maxl,f[v][]);//强制v不选
uu++; dp(u,); maxl=max(maxl,f[u][]);//强制u不选
ok=true;
continue;
}
deep[v]=deep[u]+; father[v]=u; dui[++tail]=v;
}
}
if(ok) ans+=maxl;
else {
uu++; dp(x,);
ans+=max(f[x][],f[x][]);
}
} inline void work(){
n=getint(); RG int x; ecnt=;
for(RG int i=;i<=n;i++) {
val[i]=getint(); x=getint();
next[++ecnt]=first[i]; first[i]=ecnt; to[ecnt]=x;
next[++ecnt]=first[x]; first[x]=ecnt; to[ecnt]=i;
}
for(RG int i=;i<=n;i++) if(!vis[i]) find(i);
printf("%lld",ans);
} int main()
{
work();
return ;
}