中文题意

给出n个节点的一棵树,每个点带有点权,并且下面n行第行第一个数代表它的父亲是谁,第二个数是权值。
当输入父亲是-1的说明它是根节点。
现在如果你要选择一个节点u,仅当你选择的它以及它的子树中全部的点它们的子节点个数都是偶数个,询问你可以选到最大的权值和是多少。

Solution

树形dp的味道已经很明显了,我们使用数组,代表u子树包含了u这个节点都选了偶数个点(0),和存在奇数个点(1),分别的最优解。我们先不看的权值,初始化的值为负无穷,因为我们更新第一棵子树的时候,只能假设前面有一个子节点为0的子树去更新,并且只有偶数没有奇数,但是第二棵子树开始,就可以借助选择前面的奇数个点的最大者或者选择偶数个点的最大值改变奇偶性。
那么状态转移就是,先暂时不考虑选择节点u的权值,去寻找子树可以构成的最优解


处理完最优解之后,看下是不是选择当前节点的权值会更优。并且无法更新因为如果要更新只能来源于但是它以及存在奇数个点的地方了。
但是你会发现上面的状态存在重叠部分,如果直接去更新,会发生叠加,所以要先暂存一下之前的答案,用不变的值去更新,还要记得初始化每个节点初始选择奇数个节点的权值为无穷小,不然也会出BUG。

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define rep(i, sta, en) for(int i=sta; i<=en; ++i)
#define repp(i, sta, en) for(int i=sta; i>=en; --i)
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); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
struct Node {
    ll val;
    int id;
    bool operator < (const Node& opt) const {
        return val < opt.val;
    }
};

const int N = 2e5 + 7;
ll n, m;
vector<int> edge[N];
ll f[N][2], w[N];

void dfs(int u) {
    f[u][1] = -INF;
    for (auto& v : edge[u]) {
        dfs(v);
        ll x0 = f[u][0], x1 = f[u][1];
        f[u][0] = max(x0 + f[v][0], x1 + f[v][1]);
        f[u][1] = max(x1 + f[v][0], x0 + f[v][1]);
    }
    f[u][1] = max(f[u][1], f[u][0] + w[u]);
}

void solve() {
    n = read();
    int rt = -1;
    rep(i, 1, n) {
        int fa = read();
        w[i] = read();
        if (fa == -1) {
            rt = i;
            continue;
        }
        edge[fa].push_back(i);
    }
    dfs(rt);
    ll ans = max(f[rt][0], f[rt][1]);
    print(ans);
}

int main() {
    //int T = read();    while (T--)
    solve();
    return 0;
}