做法1：

1.通过并查集维护连通性找出所有基环树的环的起点终点

2.对于每一个起点终点dfs不选这个点（和没有上司的舞会一摸一样的dfs），取max累加答案

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>

using namespace std;
//================================
#define debug(a) cout << #a": " << a << endl;
#define rep(i, ll,rr) for(int i = ll; i <= rr; ++i)
const int N =2e6+10,INF = 1e9;
//================================
typedef pair<int,int> pii;
#define x first
#define y second
typedef long long LL; typedef unsigned long long ULL; typedef long double LD;
inline LL read() { LL s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(LL x, int op = 10) { if (!x) { putchar('0'); if (op)  putchar(op); return; }  char F[40]; LL tmp = x > 0 ? x : -x; if (x < 0)putchar('-');  int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op) putchar(op); }
//================================= 
int n,m,e[N],ne[2*N],h[N],node[N],idx=0,x,y,ans=0;
LL fa[N],f[N][2];
bool st[N],ins[N];
vector<pii> root;
/*
先使用并查集维护出所有基环树的断开的两个结点
对每一棵基环树各跑一遍两棵子树都不选
*/
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

int find(int x){
    return x==fa[x]?fa[x]:find(fa[x]);
}

LL dfs(int u,int p){
    f[u][0] = 0,f[u][1] = node[u];
    for(int i=h[u];~i;i=ne[i]){
        int j = e[i];
        if(j==p) continue;
        dfs(j,u);
        f[u][0] += max(f[j][0],f[j][1]);
        f[u][1] += f[j][0];
    }
    return f[u][0];
}

signed main(){
    memset(h,-1,sizeof h);
    n = read();
    rep(i,1,n) fa[i] = i; //初始化并查集
    rep(i,1,n){
        node[i]=read(),x=read();
        int pa=find(i),pb=find(x);
        if(pa!=pb){
            fa[pa]=pb;
            add(x,i),add(i,x);
        }
        else
            root.push_back({i,x});
    }
    LL sum = 0;
    for(auto u:root)
        sum += max(dfs(u.x,-1),dfs(u.y,-1));
    printf("%lld\n",sum);
    return 0;
}

做法2：

对于基环树森林

1.找出所有环

2.对于每一个环做dfs分别得到选起点和不选起点的答案取max

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;
//================================
#define debug(a) cout << #a": " << a << endl;
#define rep(i, ll,rr) for(int i = ll; i <= rr; ++i)
const int N =1e6+10,INF = 1e9;
//================================
typedef pair<int,int> pii;
#define x first
#define y second
typedef long long LL; typedef unsigned long long ULL; typedef long double LD;
inline LL read() { LL s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(LL x, int op = 10) { if (!x) { putchar('0'); if (op)  putchar(op); return; }  char F[40]; LL tmp = x > 0 ? x : -x; if (x < 0)putchar('-');  int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op) putchar(op); }
//================================= 
int n,e[N],node[N],h[N],rm[N],ne[N],idx=0;
LL f1[N][2],f2[N][2],ans=0;
bool st[N],ins[N];

inline void add(int a,int b){
    e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}

void dfs_f(int u,int avo,LL f[][2]){
    //f[u][0] = 0;
    for(int i = h[u];~i; i = ne[i]){
        if(rm[i]) continue; //被斩断之边
        int j = e[i];
        dfs_f(j,avo,f);
        f[u][0] += max(f[j][0],f[j][1]);
    }
    f[u][1]=-INF;
    if(u!=avo){
        f[u][1] = node[u];
        for(int i=h[u];~i;i=ne[i]){
            if(rm[i]) continue;
            int j = e[i];
            f[u][1] += f[j][0];
        }
    }
}

void dfs_s(int u){
    st[u] = ins[u] = true;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(!st[j]) dfs_s(j);
        else if(ins[j]){
            rm[i] = 1;
            dfs_f(j,-1,f1);
            dfs_f(j,u,f2);
            ans+=max(f1[j][0],f2[j][1]);
        }
    }
    ins[u]=false;
}

signed main(){
    memset(h,-1,sizeof h);
    n = read();
    rep(i,1,n){
        int a= read(),b=read();
        add(b,i);
        node[i] = a;
    }
    rep(i,1,n)
        if(!st[i])
            dfs_s(i);
    
    print(ans);
    return 0;
}