【*1900 换根DP】CF1092F

怼烎@ 2024-03-16 20:12 64阅读 0赞

感觉很简单，根本没有1900的难度

[CF1092F Tree with Maximum Cost - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)y][CF1092F Tree with Maximum Cost - _ _ _ _luogu.com.cn_y]

题意：

![fd83ab482728492fac08eb90e9f7ae27.png][]

思路：

考虑换根DP

首先先树形DP，然后dfs换根

设dp\[u\]为在以u为根的子树上，所有点的贡献

dp\[u\]=dp\[v\]+sz\[v\]

然后考虑换根，可以注意到u子树部分深度加1，v子树部分深度-1，因此方程就是dp\[v\]=dp\[u\]+sum-sz\[v\]-sz\[v\]

如果要直观算贡献，一般是将u子树去掉v的那部分和v子树分开来考虑变化量

如果实在想不清楚，可以手推样例：（这里是样例1）

![32d2d9a992f348c88ce88d8f6598997b.jpeg][]

如果样例手摸不清楚，**可以给每一部分的子树设一个点，然后计算delta（变化量）**

就像这样：

![beceb2d3cf7b413aa6308cd0f2a7cfc8.jpeg][]

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    using i64 = long long;
    
    const int mxn=1e6+10;
    const int mxe=1e6+10;
    const int mod=1e9+7;
    
    struct ty{
        int to,next;
    }edge[mxe<<2];
    
    int N,u,v;
    int tot=0,sum=0;
    int a[mxn];
    int head[mxn];
    int dp[mxn],sz[mxn];
    
    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 dfs1(int u,int fa){
        sz[u]=a[u];
        for(int i=head[u];~i;i=edge[i].next){
            if(edge[i].to==fa) continue;
            dfs1(edge[i].to,u);
            sz[u]+=sz[edge[i].to];
            dp[u]+=dp[edge[i].to]+sz[edge[i].to];
        }
    }
    void dfs2(int u,int fa){
        for(int i=head[u];~i;i=edge[i].next){
            if(edge[i].to==fa) continue;
            dp[edge[i].to]=dp[u]-sz[edge[i].to]+sum-sz[edge[i].to];
            dfs2(edge[i].to,u);
        }
    }
    void solve(){
        cin>>N;
        G_init();
        for(int i=1;i<=N;i++) cin>>a[i],sum+=a[i];
        for(int i=1;i<=N-1;i++){
            cin>>u>>v;
            add(u,v);
            add(v,u);
        }
        dfs1(1,0);
        dfs2(1,0);
        int ans=0;
        for(int i=1;i<=N;i++) ans=max(ans,dp[i]);
        cout<<ans<<'\n'; 
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[CF1092F Tree with Maximum Cost - _ _ _ _luogu.com.cn_y]: https://www.luogu.com.cn/problem/solution/CF1092F
[fd83ab482728492fac08eb90e9f7ae27.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/6a6fff2828074019ae0fb9c9189427b6.png
[32d2d9a992f348c88ce88d8f6598997b.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/db9ef16ca9994cb78c68c8d735dfde4a.png
[beceb2d3cf7b413aa6308cd0f2a7cfc8.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/fd7006b2c9774fa9b2044c4972ef524f.png