一、树学

题意

由n个点组成的一棵树，现在可以以任意结点为根，求所有点最小的深度和为多少

题解

考虑换根，先看雨巨的图：

没错，如果考虑某个结点的子结点为根，这样：该结点x和除了选择的子结点y以外的结点及其子树的深度都将+1，而y及其子树的所有结点深度-1；这样一来可以构造状态转移方程：
dp[y]=dp[x]-cnt[y]+(n-cnt[y])（其中cnt[i]为i结点的所有子结点的个数（包括自身））

然后回到求cnt[]数组的问题，显然跑一遍dfs即可，像树的问题：基本上都是边跑dfs边存相关状态就能解决

AC代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
const int maxn=1e6+5;
using namespace std;
struct node{
    int nxt,to;
}edge[maxn<<1];
int head[maxn],tot;
int n,x,y;
int dep[maxn],cnt[maxn],dp[maxn];  //dep[i]：i节点的深度、cnt[i]：i节点及其子节点的个数、dp[i]：以i节点为根的所有点深度和
void add(int u,int v){
    edge[++tot].to=v;
    edge[tot].nxt=head[u];
    head[u]=tot;
}
//第一遍dfs，获取dep[],cnt[]数组
void dfs1(int u,int pre){
    for(int i=head[u];i!=-1;i=edge[i].nxt){
        int v=edge[i].to;
        if(v==pre) continue;
        dep[v]=dep[u]+1;
        dfs1(v,u);
        cnt[u]+=cnt[v];
    }
}
//第二遍dfs，换根后计算以每个结点为根节点的深度和
void dfs2(int u,int pre){
    for(int i=head[u];i!=-1;i=edge[i].nxt){
        int v=edge[i].to;
        if(v==pre) continue;
        dp[v]=dp[u]-cnt[v]+(n-cnt[v]);
        dfs2(v,u);
    }
}
void init(){
    memset(head,-1,sizeof(head));
    tot=0;
}
int main(){
    init();
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    for(int i=1;i<=n;i++){
        cnt[i]=1;
    }
    dfs1(1,0);
    //首先假定1为根节点
    for(int i=1;i<=n;i++){
        dp[1]+=dep[i];
    }
    dfs2(1,0);
    int ans=inf;
    for(int i=1;i<=n;i++){
        ans=min(ans,dp[i]);
    }
    //getchar();
    printf("%d\n",ans);
    //getchar();
    return 0;
}

二、Accumulation Degree

题意

和上题有些许不同，这题每条边有对应的流量，需要求：以某个点为根时，使得总流量最大，问最大值是多少

题解

虽然也是换根dp，但是较上题相比会更加复杂。
又是偷雨巨的图：

首先可以以1为根，求出当前的最大流量：
1.u-v这条边，如果v是叶子结点的话，则dp1[u]=dp1[u]+val;(val为这条边的最大流量)
2.如果v不是叶子结点的话，则：dp1[u]=dp1[u]+min(dp1[v]+val);
考虑换根：
同样也是u-v这条边，
1.如果u是叶子结点的话，则：dp2[v]=dp1[v]+val;
2.如果不是叶子结点的话，则：dp2[v]=dp1[v]+min(dp2[u]-min(val,dp1[v]),val);

具体实现，则是第一遍dfs求出以1为根的最大流量，第二遍dfs考虑换根

AC代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
const int maxn=2e5+5;
using namespace std;
struct node{
    int nxt,to,val;
}edge[maxn<<1];
int head[maxn],tot;
int n,u,v,val;
int deg[maxn];   //表示结点的度数
int f1[maxn],f2[maxn];   //表示以i为根的子树中流量的最大值
void init(){
    memset(head,-1,sizeof(head));
    tot=0;
    memset(f1,0,sizeof(f1));
    memset(f2,0,sizeof(f2));
    memset(deg,0,sizeof(deg));
}
void add(int u,int v,int val){
    edge[++tot].to=v;
    edge[tot].val=val;
    edge[tot].nxt=head[u];
    head[u]=tot;
}
//第一遍dfs，获取以1为根的最大流量
void dfs1(int u,int pre){
    for(int i=head[u];i!=-1;i=edge[i].nxt){
        int v=edge[i].to,val=edge[i].val;
        if(v==pre) continue;
        dfs1(v,u);
        if(deg[v]==1) f1[u]+=val;
        else f1[u]+=min(f1[v],val);
    }
}
//第二遍dfs，换根，获取所有点轮流为根时，流量的最大值
void dfs2(int u,int pre){
    for(int i=head[u];i!=-1;i=edge[i].nxt){
        int v=edge[i].to,val=edge[i].val;
        if(v==pre) continue;
        if(deg[u]==1) f2[v]=f1[v]+val;
        else f2[v]=f1[v]+min(f2[u]-min(val,f1[v]),val);
        dfs2(v,u);
    }
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        init();
        scanf("%d",&n);
        for(int i=1;i<n;i++){
            scanf("%d%d%d",&u,&v,&val);
            add(u,v,val);add(v,u,val);
            deg[u]++,deg[v]++;
        }

        dfs1(1,0);
        f2[1]=f1[1];
        dfs2(1,0);
        int ans=0;
        for(int i=1;i<=n;i++) ans=max(ans,f2[i]);
        printf("%d\n",ans);
    }
    return 0;
}