【题意】给定n个人的ai和bi，表示第i个人能力值为ai且不能和bi同时选择，求能力值和最大的选择方案。n<=10^6。
【算法】环套树DP（基环树）
【题解】n个点n条边——基环森林（若干环套树子图）。
若原图是树，经典DP做法：f[i][0/1]表示i点选或不选的最大能力值和，则f[i][0]=Σmax{f[j][0],f[j][1]}，f[i][1]=Σf[j][0]+a[i]，j=son[i]。
找环：dfs到访问过的点，标记环上的一条边。
破环：和普通树上DP唯一的区别是，标记边两端不能同时为1，所以从两端AB开始分别进行一次树形DP，最后ans=max{f[A][0],f[B][0]}（这两个f[]是两次分别计算的结果）。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=;
int n,tot,first[maxn],A,B,a[maxn];
ll f[maxn][];
bool vis[maxn],d[maxn*];
struct edge{int v,from;}e[maxn*];
void insert(int u,int v){tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;}
void dfs(int x,int fa){
vis[x]=;
for(int i=first[x];i;i=e[i].from)if(e[i].v!=fa){
if(vis[e[i].v]){A=x;B=e[i].v;d[i]=d[i^]=;}
else dfs(e[i].v,x);
}
}
void dp(int x,int fa){
//printf("x=%d\n",x);
f[x][]=;f[x][]=a[x];
for(int i=first[x];i;i=e[i].from)if(e[i].v!=fa&&!d[i]){
//printf("y=%d\n",e[i].v);
dp(e[i].v,x);
//printf("[%lld]\n",f[e[i].v][1]);
f[x][]+=max(f[e[i].v][],f[e[i].v][]);
f[x][]+=f[e[i].v][];
}
//printf("%lld %lld\n",f[x][0],f[x][1]);
}
int main(){
scanf("%d",&n);
int v;tot=;
for(int i=;i<=n;i++){
scanf("%d%d",&a[i],&v);
insert(i,v);insert(v,i);
}
ll ans=;
for(int i=;i<=n;i++)if(!vis[i]){
dfs(i,);
dp(A,);
ll sum=f[A][];
dp(B,);
ans+=max(f[B][],sum);
}
printf("%lld",ans);
return ;
}