环套树，指的是每个连通块中点数都等于边数的无向图（称为无向环套树）或者是每个点有且只有一个前趋（称为内向环套树）或后继（称为外向环套树）的有向图，由于这个图的每个连通块当中有且只有一个环（注意，可能是自环，即长度为1的环），且这个环上的每个点都可以当作根引出一棵树，所以叫“环套树”。
对于无向环套树，先将整个图进行一次DFS，当中如果发现有逆向边（这条边第一次被发现必然是作为逆向边的，也就是起点是终点的后代），就说明找到了这个环，记录其起点和终点（注意，如果有多个连通块的话，不能退出，要继续遍历完），再不断上溯（因此在DFS过程中当然要记录父边了囧），就可以找到整个环了，然后再以环上的结点为根建树即可，这样依次处理每个连通块。
对于内向环套树（外向类似），找环更为简单，只需要任选一个点，不断去找它的前趋，同时记录找到的点序列，直到某个点在序列中出现两次为止，此时这个点以及序列中它两次出现的位置中间的所有点，就是环上的点，顺序也顺便记录下来，然后树也不用建了，直接在原图中找就行了。
对于这题，由于每个点都有且只有一个后继，所以是外向环套树，不过本沙茶更倾向于它的基图（无向图，是无向环套树），然后就是一个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;
}