Z国的骑士团是一个很有势力的组织，帮会中汇聚了来自各地的精英。他们劫富济贫，惩恶扬善，受到社会各
界的赞扬。最近发生了一件可怕的事情，邪恶的Y国发动了一场针对Z国的侵略战争。战火绵延五百里，在和平环境
中安逸了数百年的Z国又怎能抵挡的住Y国的军队。于是人们把所有的希望都寄托在了骑士团的身上，就像期待有一
个真龙天子的降生，带领正义打败邪恶。骑士团是肯定具有打败邪恶势力的能力的，但是骑士们互相之间往往有一
些矛盾。每个骑士都有且仅有一个自己最厌恶的骑士（当然不是他自己），他是绝对不会与自己最厌恶的人一同出
征的。战火绵延，人民生灵涂炭，组织起一个骑士军团加入战斗刻不容缓！国王交给了你一个艰巨的任务，从所有
的骑士中选出一个骑士军团，使得军团内没有矛盾的两人（不存在一个骑士与他最痛恨的人一同被选入骑士军团的
情况），并且，使得这支骑士军团最具有战斗力。为了描述战斗力，我们将骑士按照1至N编号，给每名骑士一个战
斗力的估计，一个军团的战斗力为所有骑士的战斗力总和。

　　第一行包含一个正整数N，描述骑士团的人数。接下来N行，每行两个正整数，按顺序描述每一名骑士的战斗力
和他最痛恨的骑士。

　　应包含一行，包含一个整数，表示你所选出的骑士军团的战斗力。

N ≤ 1 000 000，每名骑士的战斗力都是不大于 1 000 000的正整数。

 1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 #define LL long long 9 using namespace std;10 const int mxn=1000010;11 int read(){12     int x=0,f=1;char ch=getchar();13     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}14     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}15     return x*f;16 }17 struct edge{18     int v,nxt;19 }e[mxn<<1];20 int hd[mxn],mct=1;21 void add_edge(int u,int v){22     e[++mct].nxt=hd[u];e[mct].v=v;hd[u]=mct;return;23 }24 int n;25 LL w[mxn];26 int ban;27 bool vis[mxn];28 int tar,r1,r2;29 void DFS(int u,int fa){30     vis[u]=1;31     for(int i=hd[u];i;i=e[i].nxt){32         if((i^1)==fa)continue;33         int v=e[i].v;34         if(vis[v]){35             r1=u;r2=v;tar=i;36             continue;37         }38         DFS(v,i);39     }40     return;41 }42 LL f[mxn][2];43 LL ans=0;44 void DP(int u,int fa){45     f[u][0]=w[u];46     for(int i=hd[u];i;i=e[i].nxt){47         int v=e[i].v;48         if((i^1)==fa || i==ban || (i^1)==ban){49 //          f[u][1]-=f[v][0];50             continue;51         }52         DP(v,i);53         f[u][0]+=f[v][1];54         f[u][1]+=max(f[v][0],f[v][1]);55     }56     return;57 }58 int main(){59     int i,j,u,v;60     n=read();61     for(i=1;i<=n;i++){62         w[i]=read();v=read();63         add_edge(i,v);64         add_edge(v,i);65     }66     for(i=1;i<=n;i++){67         if(vis[i])continue;68         DFS(i,0);69         ban=tar;70 //      printf("%d %d %d\n",r1,r2,ban);71         DP(r1,0);72         LL res=f[r1][1];73         memset(f,0,sizeof f);74 //      ban=r1;75         DP(r2,0);76         ans+=max(res,f[r2][1]);77     }78     printf("%lld\n",ans);79     return 0;80 }