题意：
求基环树最大带权独立集。
数据范围： $N \le 1000000$
题解：
算法：树形dp
分析题意：由“每个骑士都有且仅有一个自己最厌恶的骑士（当然不是他自己）”建立有向图，将每个人 $x$ 最厌恶的人 $y$ 记为其父节点 $fa[x]=y$ ，可得每个节点有且仅有一条出边，且无自环。由于共有 $N$ 条边，所以该图为基环树。
考虑到基环树的性质，删边后必定构成一棵树。分别以删去的边连接的两端点为根节点对新树进行dp（注意不能这两个端点不能同时选），再对两个结果取最大值。用 $dp[u][0/1]$ 表示以$u$为根节点的子树不选/选 $u$ 的最大值。可以得出状态转移方程：
$$dp[u][0]= \sum max(dp[v][0],dp[u][1])$$
$$dp[u][1]= \sum max(dp[v][0])$$
其中 $v$ 为 $u$ 的子节点。
此外，注意开 $long\ long$。
代码：
#include<iostream>
#include<cstdio>
using namespace std;
#define LL long long
const int N=1000010;
struct edge{
int nxt,to;
}e[N];
int n,a;
int cnt,rt;
LL ans;
int c[N],head[N],fa[N];
LL dp[N][2];
bool vis[N];
template <typename T>
inline T Max(T a,T b){
return a>b?a:b;
}
inline void add(int u,int v){
e[++cnt]=(edge){head[u],v};
head[u]=cnt;
}
void dfs(int u){
vis[u]=1;
dp[u][0]=0,dp[u][1]=c[u];
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v!=rt){
dfs(v);
dp[u][0]+=Max(dp[v][0],dp[v][1]);
dp[u][1]+=dp[v][0];
}
else dp[v][1]=-N;
}
}
inline void findC(int u){
vis[u]=1;
rt=u;
for(;!vis[fa[rt]];){
rt=fa[rt];
vis[rt]=1;
}
dfs(rt);
LL t=Max(dp[rt][0],dp[rt][1]);
vis[rt]=1;
rt=fa[rt];
dfs(rt);
ans+=Max(t,Max(dp[rt][0],dp[rt][1]));
}
signed main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&c[i],&a);
add(a,i);
fa[i]=a;
}
for(int i=1;i<=n;i++)
if(!vis[i])
findC(i);
printf("%lld",ans);
return 0;
}