<题目链接>
题目大意：
Z国的骑士团是一个很有*的组织，帮会中汇聚了来自各地的精英。他们劫富济贫，惩恶扬善，受到社会各界的赞扬。最近发生了一件可怕的事情，邪恶的Y国发动了一场针对Z国的侵略战争。战火绵延五百里，在和平环境中安逸了数百年的Z国又怎能抵挡的住Y国的军队。于是人们把所有的希望都寄托在了骑士团的身上，就像期待有一个真龙天子的降生，带领正义打败邪恶。骑士团是肯定具有打败邪恶*的能力的，但是骑士们互相之间往往有一些矛盾。每个骑士都有且仅有一个自己最厌恶的骑士（当然不是他自己），他是绝对不会与自己最厌恶的人一同出征的。战火绵延，人民生灵涂炭，组织起一个骑士军团加入战斗刻不容缓！国王交给了你一个艰巨的任务，从所有的骑士中选出一个骑士军团，使得军团内没有矛盾的两人（不存在一个骑士与他最痛恨的人一同被选入骑士军团的情况），并且，使得这支骑士军团最具有战斗力。为了描述战斗力，我们将骑士按照1至N编号，给每名骑士一个战斗力的估计，一个军团的战斗力为所有骑士的战斗力总和。
解题分析：
比较经典的基环树(环套树)。本题给出一个$n$条边$n$个点的有向图，我们可以发现，因为本题有向边表示这两个人至多只能出现其中一个，是用来表示一种关系的，所以在实际意义上，完全可以用无向边来代替。于是，本题就转化成了基环树森林，基环树的主要突破口就是要找出每个基环树的环(每个连通分量都是一颗基环树)，然后将环中的一条边拆掉，使其变成一棵树，分别以拆掉的边的两个端点作为树的根，然后进行树形DP。本题就变成了对于树上有关系的两个点，只能选一个，使得最后的总价值最大，这就变成了一个比较经典的树形DP模型(比如上司的舞会)。
注意拆环的时候，强制一个点为根，并且不选，因为尽管我们拆除了那条边，但它还是正实存在的，所以只有不选的状态才能避免这两个点都被选中(防止违反题意)。
#include <bits/stdc++.h>
using namespace std; #define clr(a,b) memset(a,b,sizeof(a))
#define REP(i,s,t) for(int i=s;i<=t;i++)
const int N = 1e6+;
typedef long long ll;
struct Edge{ int to,nxt; }e[N<<];
int n,m,cnt,head[N];
int Ecut,rt,urt;
int w[N],vis[N];
ll dp[N][]; inline void init(){
cnt=;clr(head,-);clr(vis,);clr(dp,);
}
inline void add(int u,int v){ e[cnt]=(Edge){ v,head[u] };head[u]=cnt++; } void dfs(int u,int pre){
vis[u]=;
for(int i=head[u];~i;i=e[i].nxt){
int v=e[i].to;
if(v==pre)continue;
if(!vis[v])dfs(v,u);
else { //如果找到环了
rt=u,urt=v,Ecut=i; //记录下这个环的两个端点，并且记录这个拆除的边
}
}
}
void trdp(int u,int pre){
dp[u][]=w[u]; //表示选当前这个点的价值
dp[u][]=; //表示不选当前这个点的价值
for(int i=head[u];~i;i=e[i].nxt){
int v=e[i].to;
if(i==Ecut || i==(Ecut^) || v==pre)continue;
trdp(v,u);
dp[u][]+=dp[v][];
dp[u][]+=max(dp[v][],dp[v][]);
}
}
int main(){
while(~scanf("%d",&n)){
init();
REP(i,,n){
int now;scanf("%d%d",&w[i],&now);
add(i,now);add(now,i);
}
ll sum=;
REP(i,,n) if(!vis[i]) {
dfs(i,-); //基环树森林，每个连通分量中必有一个环
trdp(rt,-); //以拆分的两个点分别为根，进行树形DP
ll tmp = dp[rt][];
trdp(urt,-);
sum+=max(tmp,dp[urt][]);
}
printf("%lld\n",sum);
}
}