[CF 533B] Work Group

作法：

蠻基本的樹上的DP題，記 dp[ x ][ 0 ] 代表以 x 為根的子樹中，選偶數個人並且滿足條件的最大價值，dp[ x ][ 1 ] 則是選奇數個人( 不管 x 本身是否有選 )，那麼在算 dp[ x ]的時候，首先算出不取 x 的話，在他的子樹中取奇數或偶數個人，並且滿足條件的最大價值，然後再拿「取 x 並且在他的子樹中取偶數個人」的價值去更新取奇數個人的價值就可以了。

code :

#include<bits/stdc++.h>
#define LL long long
#define INF (1LL<<60)
using namespace std;
const int maxn=200000+10 ;
 
vector<int> v[maxn] ;
int fa[maxn],val[maxn] ;
LL dp[maxn][2] ;
 
void dfs(int x)
{
    if(v[x].empty())
    {
        dp[x][0]=0 ;
        dp[x][1]=val[x] ;
        return ;
    }
    for(auto i : v[x]) dfs(i) ;
 
    dp[x][1]=-INF ;
    for(auto i : v[x])
    {
        LL t0=dp[x][0] , t1=dp[x][1] ;
        dp[x][0]=max(t0+dp[i][0],t1+dp[i][1]) ;
        dp[x][1]=max(t1+dp[i][0],t0+dp[i][1]) ;
    }
    dp[x][1]=max(dp[x][1],dp[x][0]+val[x]) ;
}
 
main()
{
    int n ; scanf("%d",&n) ;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&fa[i],&val[i]) ;
        if(i!=1) v[fa[i]].push_back(i) ;
    }
    dfs(1) ;
    printf("%I64d\n",max(dp[1][0],dp[1][1])) ;
}