Work Group

标签：ch Group 奇数 res Work 偶数 putchar define

analysis

我们很明显能够发现这个题目的性质：

1. 奇数是由孩子的奇数和我的偶数，或者是孩子的偶数我的奇数取一个最大值进行更新。
2. 偶数就是我的偶数和孩子的偶数，或者是孩子奇数和我的奇数取一个最大值进行更新。

我们不妨用 \(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;
}

标签：ch,Group,奇数,res,Work,偶数,putchar,define
From： https://www.cnblogs.com/carp-oier/p/17770621.html