analysis
我们很明显能够发现这个题目的性质：
- 奇数是由孩子的奇数和我的偶数，或者是孩子的偶数我的奇数取一个最大值进行更新。
- 偶数就是我的偶数和孩子的偶数，或者是孩子奇数和我的奇数取一个最大值进行更新。
我们不妨用 \(0\) 表示已经选择了偶数个节点，用 \(1\) 表示已经选择了奇数个节点。
易得我们这个题目的转移方程为：
\[f_{u, 0} \gets \max(f_{v, 0} + f_{u, 0}, f_{v, 1} + f_{u, 1})
\]
\[f_{u, 1} \gets \max(f_{v, 1} + f_{u, 0}, f_{v, 0} + f_{u, 1})
\]
code time
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rl register ll
#define foa(i, a, b) for(rl i=a; i < b; ++ i)
#define fos(i, a, b) for(rl i=a; i <= b; ++ i)
#define fop(i, a, b) for(rl i=a; i >= b; -- i)
#define ws putchar(' ')
#define wl putchar('\n')
template <class T> inline void waw(T x)
{
if(x > 9) waw(x / 10);
putchar(x % 10 ^ 48);
}
template <class T> inline void ww(T x)
{
if(x < 0) x = ~x + 1, putchar('-');
waw(x);
}
template <class T> inline void read(T &res)
{
char ch = getchar(); bool f = 0; res = 0;
for(; !isdigit(ch); ch = getchar()) f |= ch == '-';
for(; isdigit(ch); ch = getchar()) res = (res << 1) + (res << 3) + (ch ^ 48);
res = f ? ~res + 1 : res;
}
const ll N = 2e5 + 10, M = N << 1;
ll n, m, w[N], f[N][2];
ll tot, h[N];
struct edge { ll v, ne; } e[M];
inline void add(ll a, ll b) { e[ ++ tot] = {b, h[a]}, h[a] = tot; }
inline void dfs(ll u, ll fa)
{
f[u][1] = -1e18;
for(rl i=h[u]; ~i; i = e[i].ne)
{
ll v = e[i].v;
if(v == fa) continue;
dfs(v, u);
ll x = f[u][1], y = f[u][0];
f[u][0] = max(f[v][1] + x, f[v][0] + y);
f[u][1] = max(f[v][1] + y, f[v][0] + x);
}
f[u][1] = max(f[u][1], f[u][0] + w[u]);
}
int main()
{
read(n);
tot = -1, memset(h, -1, sizeof h);
fos(i, 1, n)
{
ll a, b; read(a), read(b);
if(a != -1) add(a, i), add(i, a); w[i] = b;
}
dfs(1, -1);
cout << max(f[1][0], f[1][1]) << endl;
return 0;
}