<div class="post_brief"><p>
多少年前的坑了。</p>

 

用mac写的第一篇题解呢。

 

环套树DP。先把树上的情况处理了，然后枚举取不取环上的第一个。

 

要注意会有重边的情况，比较恶心。

 

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>

using namespace std;


const int buf_len = 4000;
char buf[buf_len], *bufb(buf), *bufe(buf + 1);
#define readBuf() { 

if (++ bufb == bufe) 

bufe = (bufb = buf) + fread(buf, 1, sizeof(buf), stdin); 

}
#define readInt(x) { 

register int s(0); 

do { 

readBuf(); 

} while (!isdigit(*bufb)); 

do { 

s = s * 10 + *bufb - 48; 

readBuf(); 

} while (isdigit(*bufb)); 

x = s; 

}


typedef long long dint;
#ifdef WIN32
#define lld “%I64d”
#else
#define lld “%lld”
#endif


struct edge {
int t;
edge *next;
};


const int maxn = 1000009;


int n, v[maxn];
int stc[maxn], tst, lpp[maxn], tlp;
int vis[maxn], onl[maxn];
dint f[maxn], g[maxn];
edge elst[maxn << 1], *ep(elst), *head[maxn];


inline void addEdge(int u, int v) {
ep-> t = v;
ep-> next = head[u];
head[u] = ep ++;
}


void dfsLoop(int p, int fr) {
vis[p] = fr + 1;
stc[tst ++] = p;
for (edge* e = head[p]; e; e = e-> next)
if (e-> t != fr) {
if (!vis[e-> t]) {
dfsLoop(e-> t, p);
}
else if (vis[e-> t] && vis[e-> t] != p + 1) {
if (onl[p])
continue;
tlp = 0;
do {
– tst;
lpp[tlp ++] = stc[tst];
onl[stc[tst]] = 1;
} while (stc[tst] != e-> t);
}
}
if (stc[tst - 1] == p)
– tst;
}


void dfsDP(int p, int fr) {
f[p] = 0;
g[p] = v[p];
vis[p] = -1;
for (edge* e = head[p]; e; e = e-> next)
if (e-> t != fr && !onl[e-> t] && vis[e-> t] != -1) {
dfsDP(e-> t, p);
f[p] += max(f[e-> t], g[e-> t]);
g[p] += f[e-> t];
}
}


dint calcCC(int p) {
tst = 0;
tlp = 0;
dfsLoop(p, 0);
if (!tlp)
lpp[tlp ++] = p;
for (int i = 0; i < tlp; ++ i)
dfsDP(lpp[i], 0);
dint s0(0), s1(0);
if (tlp < 3) {
for (int i = 0; i < tlp; ++ i)
s0 = max(s0, g[lpp[i]] - f[lpp[i]]);
for (int i = 0; i < tlp; ++ i)
s0 += f[lpp[i]];
}
else {
dint f0(g[lpp[0]] + f[lpp[1]] + f[lpp[tlp - 1]]), g0(f0);
for (int i = 2; i < tlp - 1; ++ i) {
dint f1(f[lpp[i]] + max(f0, g0)), g1(g[lpp[i]] + f0);
f0 = f1;
g0 = g1;
}
s0 = max(f0, g0);
}
if (tlp < 3) {
s1 = s0;
}
else {
dint f0(f[lpp[0]]), g0(f0);
for (int i = 1; i < tlp; ++ i) {
dint f1(f[lpp[i]] + max(f0, g0)), g1(g[lpp[i]] + f0);
f0 = f1;
g0 = g1;
}
s1 = max(g0, f0);
}
return max(s0, s1);
}


int main() {
#ifndef ONLINE_JUDGE
freopen(“in.txt”, “r”, stdin);
#endif


readInt(n);
memset(head, 0, sizeof(head));
for (int i = 1; i &lt;= n; ++ i) {
	int x;
	readInt(v[i]);
	readInt(x);
	addEdge(i, x);
	addEdge(x, i);
}
memset(vis, 0, sizeof(vis));
memset(onl, 0, sizeof(onl));
dint ans(0);
for (int i = 1; i &lt;= n; ++ i)
	if (!vis[i])
		ans += calcCC(i);
printf(lld "\n", ans);



}