Work Group

题意：
有一颗n个节点并且以1为根的树，每一个节点有一个权值，你可以选择一些节点组成工作组，工作中中的每一个节点他的子树上的节点在工作组的数目为偶数（不包括自己），求工作组的最大权值为多少（工作组的权值等于工作组中每个节点的权值之和）？

思路：
树状dp
dp[v][0/1]表示第v个节点在满足条件时该子树在工作组的个数为偶数/奇数的最大权值。
首先初始化：(一开始不包括v节点)
dp[v][0]=0;
dp[v][1]=-inf;（极小值表示不存在）
然后加入子树u：
dp[v][0]=max(dp[v][1]+dp[u][1],dp[v][0]+dp[u][0]);(奇数+奇数=偶数，偶数+偶数=偶数)
dp[v][1]=max(dp[v][1]+dp[u][0],dp[v][0]+dp[u][1]);(奇数+偶数=奇数，偶数+奇数=偶数)
最后加入v节点：
dp[v][0]不变，因为加入v节点成偶数则需要子树共有奇数个节点，不符合条件，所以偶数个一定不包括根节点。
dp[v][1]=max(dp[v][0]+val[v],dp[v][1]);

代码：

#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

typedef long long ll;
const ll inf=998244353;
const int N=200005;

ll val[N], dp[N][2];
vector<int> g[N];

void dfs(int v)
{
    dp[v][0]=0;
    dp[v][1]=-inf;
    for(int i=0;i<g[v].size();i++)
    {
        int u=g[v][i];
        dfs(u);
        ll tmp=max(dp[v][0]+dp[u][0],dp[v][1]+dp[u][1]);   //对计算后的dp[v][0]先保存，防止对计算dp[v][1]造成影响。
        dp[v][1]=max(dp[v][0]+dp[u][1],dp[v][1]+dp[u][0]);
        dp[v][0]=tmp;
    }
    dp[v][1]=max(dp[v][1],dp[v][0]+val[v]);
}

int main()
{
    int n;
    scanf("%d",&n);
    ll sum=0, mi=inf;
    for(int i=1;i<=n;i++)
    {
        ll a;
        scanf("%lld%lld",&a,&val[i]);
        if(a!=-1)
        {
            g[a].push_back(i);
        }
    }
    dfs(1);
    cout << max(dp[1][0],dp[1][1]) << endl;
    return 0;
}