【每日一题0413】树型dp+换根

201400 树学

n个点和n-1条边（树），选择一个点作为根节点使得所有点的深度和最小。

用表示以i为根的时候的深度和，表示i子树含有的节点和； 每个节点的深度；
假设u是v的父亲；则

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 1e6 + 5;
#define N 1000005
ll tot,dis[N],fa[N],h[N],ne[N<<1],p[N<<1],wi[N<<1];
void addEdge(int u,int v,int w){p[++tot]=v;ne[tot]=h[u];h[u]=tot;wi[tot]=w;}
void add(int u,int v){p[++tot]=v;ne[tot]=h[u];h[u]=tot;}
void addOrEdge(int u,int v){ne[++tot]=h[u];h[v]=tot;}
ll num[MAXN],dep[MAXN];ll siz[MAXN]={0};
ll f[MAXN];int ton;
void dfs(int u,int father){
    siz[u]=1;
    for(int i=h[u];i;i=ne[i])if(p[i]!=father){
        dep[p[i]]=dep[u]+1;
        dfs(p[i],u);
        siz[u]+=siz[p[i]];
    }
}
ll ans=INT_MAX;
void dfs2(int u,int father){
    siz[u]=1;
    for(int i=h[u];i;i=ne[i])if(p[i]!=father){
        f[p[i]]=f[u]-siz[p[i]]+ton-siz[p[i]];
        ans=min(ans,f[p[i]]);
        dfs2(p[i],u);
    }
}

signed main()
{
    int n;cin>>n;ton=n;
    for(int i=1;i<n;++i){
        int u,v;cin>>u>>v;
        add(u,v);add(v,u);
    }
    dep[1]=0;
    dfs(1,0);
    ll sum=0;
    for(int i=1;i<=n;++i){
        sum+=dep[i];
    }
    f[1]=ans=sum;
    dfs2(1,0);
    cout<<ans<<endl;
    return 0;
}

换根思想

即先算出固定某一点为根的答案然后考虑把它的儿子换成根会发生什么样的变化，如果这个变化是比较好算的，那么我们就可考虑每个点x为根的答案都根据以它父亲为根的结果去推。

NC51180 Accumulation Degree

最大难度在于读题
给你一颗有 n 个节点的树,edge(i,j)表示流量最大值；找一个根，使得根到所有叶子节点的流量和为最大值。
定义表示以 i 为根的子树中流量最大值。

• v为叶子节点，那么
• v为非叶子节点，那么
  换根:
  dfs1的用d[i]来表示以 i 为根的子树中流量最大值
  f[i]表示以i为根时候根到所有叶子节点的流量和。
  转移的贡献是

#include <bits/stdc++.h>
using namespace std;

#define ll long long
const int MAXN = 2e5 + 10;
#define N 200010
ll tot,dis[N],fa[N],h[N],ne[N<<1],p[N<<1],wi[N<<1],d[N],f[N];
void addEdge(int u,int v,int w){p[++tot]=v;ne[tot]=h[u];h[u]=tot;wi[tot]=w;}
void add(int u,int v){p[++tot]=v;ne[tot]=h[u];h[u]=tot;}
void addOrEdge(int u,int v){ne[++tot]=h[u];h[v]=tot;}
ll num[MAXN],inDe[MAXN];ll siz[MAXN]={0};
void dfs(int u,int father){
    for(int i=h[u];i;i=ne[i])if(p[i]!=father){
        dfs(p[i],u);
        if(inDe[p[i]]==1)d[u]+=wi[i];
        else d[u]+=min(wi[i],d[p[i]]);
    }
}
void dfs2(int u,int father){
    for(int i=h[u];i;i=ne[i])if(p[i]!=father){
        int v=p[i];
        if(inDe[u]==1)f[v]=d[v]+wi[i];
        else f[v]=d[v]+min(f[u]-min(wi[i],d[v]),wi[i]);
        dfs2(v,u);
    }
}
signed main()
{
    int t;
    cin>>t;
    while(t--){
        int n;cin>>n;
        tot=0;memset(h,0,sizeof(h));memset(d,0,sizeof(d));memset(f,0,sizeof(f));
        memset(inDe,0,sizeof(inDe));
        for(int i=1;i<n;i++){
            int u,v,w;
            scanf("%d %d %d",&u,&v,&w);
            addEdge(u,v,w);addEdge(v,u,w);
            inDe[u]++;inDe[v]++;
        }
        dfs(1,0);
        f[1]=d[1];
        dfs2(1,0);
        ll ans=0;
        for(int i=1;i<=n;i++)ans=max(ans,f[i]);
        cout<<ans<<endl;
    }
    return 0;
}