環(huán)套樹，指的是每個(gè)連通塊中點(diǎn)數(shù)都等于邊數(shù)的無向圖（稱為無向環(huán)套樹）或者是每個(gè)點(diǎn)有且只有一個(gè)前趨（稱為內(nèi)向環(huán)套樹）或后繼（稱為外向環(huán)套樹）的有向圖，由于這個(gè)圖的每個(gè)連通塊當(dāng)中有且只有一個(gè)環(huán)（注意，可能是自環(huán)，即長度為1的環(huán)），且這個(gè)環(huán)上的每個(gè)點(diǎn)都可以當(dāng)作根引出一棵樹，所以叫“環(huán)套樹”。
對(duì)于無向環(huán)套樹，先將整個(gè)圖進(jìn)行一次DFS，當(dāng)中如果發(fā)現(xiàn)有逆向邊（這條邊第一次被發(fā)現(xiàn)必然是作為逆向邊的，也就是起點(diǎn)是終點(diǎn)的后代），就說明找到了這個(gè)環(huán)，記錄其起點(diǎn)和終點(diǎn)（注意，如果有多個(gè)連通塊的話，不能退出，要繼續(xù)遍歷完），再不斷上溯（因此在DFS過程中當(dāng)然要記錄父邊了囧），就可以找到整個(gè)環(huán)了，然后再以環(huán)上的結(jié)點(diǎn)為根建樹即可，這樣依次處理每個(gè)連通塊。
對(duì)于內(nèi)向環(huán)套樹（外向類似），找環(huán)更為簡(jiǎn)單，只需要任選一個(gè)點(diǎn)，不斷去找它的前趨，同時(shí)記錄找到的點(diǎn)序列，直到某個(gè)點(diǎn)在序列中出現(xiàn)兩次為止，此時(shí)這個(gè)點(diǎn)以及序列中它兩次出現(xiàn)的位置中間的所有點(diǎn)，就是環(huán)上的點(diǎn)，順序也順便記錄下來，然后樹也不用建了，直接在原圖中找就行了。
對(duì)于這題，由于每個(gè)點(diǎn)都有且只有一個(gè)后繼，所以是外向環(huán)套樹，不過本沙茶更傾向于它的基圖（無向圖，是無向環(huán)套樹），然后就是一個(gè)DP了囧……
代碼：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
#define ll long long
const int MAXN = 1000010;
const ll INF = ~0Ull >> 2;
struct edge {
int a, b, pre, next;
} E0[MAXN * 3], E[MAXN << 1];
int n, m0, m, A[MAXN], stk[MAXN], st[MAXN], pr[MAXN], Q[MAXN];
ll F[MAXN][2], res = 0;
bool vst[MAXN], vst0[MAXN];
void init_d()
{
re(i, n) E0[i].pre = E0[i].next = E[i].pre = E[i].next = i; if (n & 1) m0 = n + 1; else m0 = n; m = n;
}
void add_edge0(int a, int b)
{
E0[m0].a = a; E0[m0].b = b; E0[m0].pre = E0[a].pre; E0[m0].next = a; E0[a].pre = m0; E0[E0[m0].pre].next = m0++;
E0[m0].a = b; E0[m0].b = a; E0[m0].pre = E0[b].pre; E0[m0].next = b; E0[b].pre = m0; E0[E0[m0].pre].next = m0++;
}
void add_edge(int a, int b)
{
E[m].a = a; E[m].b = b; E[m].pre = E[a].pre; E[m].next = a; E[a].pre = m; E[E[m].pre].next = m++;
}
void init()
{
scanf("%d", &n); int x; init_d();
re(i, n) {
scanf("%d%d", &A[i], &x); add_edge0(--x, i);
}
}
void sol0(int x)
{
Q[0] = x; int i, j, front, rear;
for (front=0, rear=0; front<=rear; front++) {
i = Q[front];
for (int p=E0[i].next; p != i; p=E0[p].next) {
j = E0[p].b;
if (!vst0[j]) {Q[++rear] = j; vst0[j] = 1; add_edge(i, j);}
}
}
rre3(z, rear, 0) {
i = Q[z];
F[i][0] = 0; F[i][1] = A[i];
for (int p=E[i].next; p != i; p=E[p].next) {
j = E[p].b; F[i][0] += F[j][0] >= F[j][1] ? F[j][0] : F[j][1]; F[i][1] += F[j][0];
}
}
}
void solve()
{
re(i, n) {vst[i] = vst0[i] = 0; st[i] = E0[i].next;} int x, y, tp, x0, y0; bool FF, FF2; ll tmp0, tmp1, tmp00, tmp01, res0;
re(i, n) if (!vst[i]) {
stk[tp = 0] = i; vst[i] = 1; FF2 = 0;
while (tp >= 0) {
x = stk[tp]; FF = 0;
for (int p=st[x]; p != x; p=E0[p].next) {
y = E0[p].b;
if (!vst[y]) {vst[y] = 1; stk[++tp] = y; pr[y] = p; st[x] = E0[p].next; FF = 1; break;}
else if (p != (pr[x] ^ 1) && !FF2) {FF2 = 1; x0 = x; y0 = y;}
}
if (!FF) tp--;
}
if (FF2) {
tp = 0; vst0[y0] = 1; while (x0 != y0) {stk[tp++] = x0; vst0[x0] = 1; x0 = E0[pr[x0]].a;} stk[tp++] = y0;
re(j, tp) sol0(stk[j]);
tmp0 = F[stk[0]][0]; tmp1 = -INF;
re2(j, 1, tp) {
tmp00 = (tmp0 >= tmp1 ? tmp0 : tmp1) + F[stk[j]][0];
tmp01 = tmp0 + F[stk[j]][1];
tmp0 = tmp00; tmp1 = tmp01;
}
res0 = tmp0 >= tmp1 ? tmp0 : tmp1;
tmp0 = -INF; tmp1 = F[stk[0]][1];
re2(j, 1, tp) {
tmp00 = (tmp0 >= tmp1 ? tmp0 : tmp1) + F[stk[j]][0];
tmp01 = tmp0 + F[stk[j]][1];
tmp0 = tmp00; tmp1 = tmp01;
}
res += res0 >= tmp0 ? res0 : tmp0;
}
}
}
void pri()
{
cout << res << endl;
}
int main()
{
init();
solve();
pri();
return 0;
}