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

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

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

今天打算小学一手换根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;
}