【换根DP】CF1187E Tree Painting

墨蓝 2024-03-17 11:26 55阅读 0赞

[Problem - 1187E - Codeforces][]

题意：

![d94ac9a14f4a4226b7bf5066e0999bd6.png][]

![9b85caada3e445238536cecad85023a8.png][]

思路：

有限制的最值问题，很自然地想到换根DP

在考虑换根DP的时候，先把以1为根的答案求出来，即先把fi求出来，这个时候就用普通的树形DP求，**dp数组对应的主体是子树，在状态转移的时候考虑的主体也是子树，在定义的时候记得把贡献说清楚，因为根据树形DP都是算贡献题，只有弄清楚要算的是什么贡献，才能正确地转移**

**所以树形DP在状态转移的时候需要考虑一下一般算贡献是怎么算的**

然后在考虑换根的时候，因为以1作为根的答案f已经算出来了，换根之后，根据刚刚的转移方式，看看v的父节点u部分的去掉v的子树的新子树能不能用u的儿子和其他参数表示

![9a1664827ebcb9f638151053a05478d8.png][]

即在上图中结点 j 的贡献能不能用 j 子树除去 i 子树的部分（用已经算出来的f数组表示）和i部分的子树（不能用f数组表示，因为fi表示的子树包括了i现在的父亲），当然有时候可以用容斥，大部分情况是用其他参数表示（参考f数组的转移方式）

![93ded22a2e8f4ac5bafc7e00bce5af3f.png][]

![af256ecb7cb74270aa4ad64c8a37b078.png][]

Code：

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

[Problem - 1187E - Codeforces]: https://codeforces.com/problemset/problem/1187/E
[d94ac9a14f4a4226b7bf5066e0999bd6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/9789958d498f477e8f62845a1d3cb9d1.png
[9b85caada3e445238536cecad85023a8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/1567ff1848654463878a079e367ab78f.png
[9a1664827ebcb9f638151053a05478d8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/93db5e3efbe2445fb6cfdb4f222d2f1a.png
[93ded22a2e8f4ac5bafc7e00bce5af3f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/8ea6d0f6ead54a88b73e088b6080bc30.png
[af256ecb7cb74270aa4ad64c8a37b078.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/bc763d0cf911459cb480e4c9c3183023.png