【*2000 树形DP】 CF533B

逃离我推掉我的手 2024-03-16 10:38 11阅读 0赞

[Problem - 533B - Codeforces][]

题意：

![cc9899eb75ec40c5aa4b42be51e2b207.png][]

![71ba6074d1de419f9e4d0838bf65e6bc.png][]

思路：

因为n<=1e5，因此不可能把第二维开成：子树中已选的人数，应该表示奇偶性

状态设计：

dp\[u\]\[0/1\]：以u为根的子树中，已选的人数的奇偶性为偶or奇的最大权值

然后进行转移

注意，树形DP转移方程一定是对于其中一棵子树而言的（比如第i棵子树）

**对于u的这么多儿子结点，可以把它们看成是这么多个物品（这里也是线性更新DP数组的），从左到右更新儿子结点的DP数组，这点很重要！**

![0c6b75d924b24b46b877b9bce371fb8c.png][]

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=2e5+10;
    const int mxe=2e5+10;
    const int Inf=1e18;
    
    struct ty{
        int to,next;
    }edge[mxe<<2];
    
    int N,tot=0;
    int p[mxn],a[mxn],head[mxn],dp[mxn][2];
    
    void add(int u,int v){
        edge[tot].to=v;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    void G_init(){
        tot=0;
        for(int i=0;i<=N;i++){
            head[i]=-1;
        }
    }
    void dfs(int u,int fa){
        dp[u][1]=-Inf;
        for(int i=head[u];~i;i=edge[i].next){
            if(edge[i].to==fa) continue;
            dfs(edge[i].to,u);
            int x=dp[u][0],y=dp[u][1];
            dp[u][0]=max(x+dp[edge[i].to][0],y+dp[edge[i].to][1]);
            dp[u][1]=max(x+dp[edge[i].to][1],y+dp[edge[i].to][0]);
        }
        dp[u][1]=max(dp[u][1],dp[u][0]+a[u]);
    }
    void solve(){
        cin>>N;
        G_init();
        for(int i=1;i<=N;i++){
            cin>>p[i]>>a[i];
            if(p[i]==-1) continue;
            add(p[i],i);
            add(i,p[i]);
        }
        dfs(1,0);
        cout<<max(dp[1][0],dp[1][1])<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[Problem - 533B - Codeforces]: https://codeforces.com/problemset/problem/533/B
[cc9899eb75ec40c5aa4b42be51e2b207.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/921d4cb31f994f5fb6b712e78a9c865b.png
[71ba6074d1de419f9e4d0838bf65e6bc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/042f0c353c5f4e6cb18e978242beba98.png
[0c6b75d924b24b46b877b9bce371fb8c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/f9072c1ee177454a88e66a7e406bea59.png