【裸换根DP】ABC220 F - Distance Sums 2 + [USACO10MAR] Great Cow Gathering G

向右看齐 2024-03-22 11:05 7阅读 0赞

**今天打算小学一手换根DP，入个门就可以！**

题意：

![c33561c8aa1b4774b50102052dde3efd.png][]

思路：

一眼换根

考虑换根DP的时候，我们考虑把以父亲作为根的贡献和以儿子作为根的贡献进行比较，用父亲推儿子

对于这道题，这样考虑贡献即可：

![2eeb03175aa1465d8e8e0beae87eb311.jpeg][]

Code：

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

## \[USACO10MAR\] Great Cow Gathering G ##

[P2986 \[USACO10MAR\] Great Cow Gathering G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)][P2986 _USACO10MAR_ Great Cow Gathering G - _ _ _ _luogu.com.cn]

这也是裸的换根

题意：

![a7d0bd333b84495e9bf8e644555aca32.png][]

思路：

![1e802df54da34853ae9ee19bf0f65f2b.jpeg][]

Code：

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

[c33561c8aa1b4774b50102052dde3efd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/bcebe25eaa0e498f9a6362e4b3c5a1bf.png
[2eeb03175aa1465d8e8e0beae87eb311.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/72443356da9b42a9abb8a075342a9266.png
[P2986 _USACO10MAR_ Great Cow Gathering G - _ _ _ _luogu.com.cn]: https://www.luogu.com.cn/problem/P2986
[a7d0bd333b84495e9bf8e644555aca32.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/b03c3a8ad35c49f1967a96321d1c1f59.png
[1e802df54da34853ae9ee19bf0f65f2b.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/9dcad544e303472abc18303f0435cd57.png