【裸换根DP】ABC220 F - Distance Sums 2 + [USACO10MAR] Great Cow Gathering G
今天打算小学一手换根DP,入个门就可以!
题意:
思路:
一眼换根
考虑换根DP的时候,我们考虑把以父亲作为根的贡献和以儿子作为根的贡献进行比较,用父亲推儿子
对于这道题,这样考虑贡献即可:
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)
这也是裸的换根
题意:
思路:
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;
}
还没有评论,来说两句吧...