牛客 Tree(最小深度总和)（两种方法求重心）难度⭐⭐⭐

题目链接

牛妹有一张连通图，由n个点和n-1条边构成，也就是说这是一棵树，牛妹可以任意选择一个点为根，根的深度 $de{p}_{root}$deproot​​为0，对于任意一个非根的点，我们将他到根节点路径上的第一个点称作他的父节点，例如1为根， $1-4$1−4的；路径为 $1-3-5-4$1−3−5−4时，4的父节点是5，并且满足对任意非根节点， $de{p}_i=de{p}_{f{a}_i}+1$depi​=depfai​​+1，整棵树的价值 $W={\sum }_{i=1}^{n}de{p}_i$W=i=1∑n​depi​ ，即所有点的深度和 牛妹希望这棵树的W最小，请你告诉她，选择哪个点可以使W最小

输入描述:

第一行，一个数，n接下来n-1行，每行两个数x,y，代表x-y是树上的一条边

输出描述:

一行，一个数，最小的W

数据范围 $1\left(30pts\right)$1(30pts): 每次换根dfs，求出对于每个点为根时的w，取min即可，复杂度 $\Theta \left(n^2\right)$Θ(n2)
数据范围 $2\left(100pts\right)$2(100pts): 考虑任意选择一个点为根算出 $K_{root}$Kroot​，对于两个相邻的点 $a,b$a,b，我们令 $si{z}_a$siza​​表示 $b$b为根时， $a$a的子树大小， $si{z}_b$sizb​为 $a$a为根时， $b$b的子树大小，那么显然在 $a,b$a,b之间转移答案的变化为 $\mid si{z}_a-si{z}_b\mid$∣siza​−sizb​∣，故单次转移的复杂度为 $O\left(1\right)$O(1)，总复杂度 $O\left(n\right)$O(n)

两种方法

注意这两种方法都必须用C++14才能AC

法1：重心法

不懂重心的点这里
先用树形DP找到树的重心，再BFS以重心为根求深度和即可

#include <bits/stdc++.h>
#define inf 100000000
#define x first
#define y second
#define pp pair<ll, ll>
using namespace std;
typedef long long ll;
const ll N = 2e6+5;
ll head[N], top = 0;
ll n;
ll son[N], vis[N];
ll ans, res, point;
struct Edge
{
    ll v, next;
}edge[N * 2];

void init()
{
    memset(head, -1, sizeof(head));
    top = 0;
    memset(son, 0, sizeof(son));
    ans = inf;
}

void addedge(ll u, ll v)
{
    edge[top].v = v;
    edge[top].next = head[u];
    head[u] = top++;
}

void dfs(ll u, ll fa)
{
    son[u] = 1;
    ll Max = 0;
    for (ll i = head[u]; i != -1; i = edge[i].next)
    {
        ll v = edge[i].v;
        if (v == fa)
            continue;
        dfs(v, u);
        son[u] += son[v];
        Max = max(Max, son[v]);
    }

    ll tmp = max(Max, n - son[u]);
    if (tmp < ans || tmp == ans && u < point)//如果相等说明有两个重心，选编号最小的那一个
    {
        ans = tmp;
        point = u;
    }
}

ll bfs()
{
    queue<pp> q;
    vis[point] = 1;//重心
    q.push(make_pair(point, 0));//点和深度
    while (!q.empty())
    {
        pp now = q.front();
        q.pop();
        for (ll i = head[now.x]; i != -1; i = edge[i].next)
        {
          ll to = edge[i].v;
          if (!vis[to])
          {
            vis[to] = 1;
            q.push(make_pair(to, now.y + 1));
            res += now.y + 1;//求的是总的深度和，所以每“递归”一次就加上+1后的深度
          }
        }
    }
}

int main()
{
    init();
    scanf("%lld", &n);
    for (ll i = 1; i < n; i++)
    {
        ll u, v;
        scanf("%lld%lld", &u, &v);
        addedge(u, v);
        addedge(v, u);
    }
    dfs(1, -1);
    bfs();
    printf("%lld\n", res);
    return 0;
}

法2：换根法

先以1为根求深度和，再BFS换根，求最小值即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 7;
int head[maxn], to[maxn<<1], nex[maxn<<1], tot;
ll dep[maxn];
int son[maxn], n;
ll ans;
  
int read()
{
    int x=0;char s=getchar();
    for( ;isdigit(s);x=x*10+s-48,s=getchar());
    return x;
}
  
  
void init()
{
    memset(head, -1, sizeof(head));
    tot = 0;
}
void add( int x, int y )
{
    to[tot] = y;
    nex[tot] = head[x];
    head[x] = tot++;
}
void dfs( int x, int fx, int deep )
{
    for ( int i = head[x]; ~i; i = nex[i] )
    {
        int v = to[i];
        if(v == fx) continue;
        dfs(v, x, deep + 1);
        son[x] += son[v];
        dep[x] += dep[v];
    }
    son[x]++, dep[x] += deep;
}
  
struct node{
    int x, fx;
}p[maxn];
  
int cnt = 0;
int vis[maxn];
  
void bfs()
{
    queue<node> que;
    vis[1] = 1;
    for ( int i = head[1]; ~i; i = nex[i] )
    {
        int v = to[i];
        que.push({v, 1});
        vis[v] = 1;
    }
    while ( !que.empty() )
    {
        node now = que.front(); que.pop();
        p[cnt].x = now.x; p[cnt++].fx = now.fx;
        int u = now.x;
        for ( int i = head[u]; ~i; i = nex[i] )
        {
            int v = to[i];
            if(vis[i]||v == now.fx) continue;
            vis[i] = 1;
            node t;
            t.x = v; t.fx = u;
            que.push(t);
        }
    }
      
  
  
    for ( int i = 0; i < cnt; i++ )
    {
        int x = p[i].x, fx = p[i].fx;
        ll tmp = dep[x];
        tmp -= son[x];
        tmp += dep[fx] - dep[x] + (n - son[x]);
        dep[x] = tmp;
          
        ans = min(ans, tmp);
    }
}
  
int main()
{
    init();
    n=read();
    for ( int i = 1; i <= n - 1; i++ )
    {
        int a=read(), b=read();
        add(a, b); add(b, a);
    }
    dfs(1, 1, 0);
    ans = dep[1];
    bfs();
    printf("%lld\n", ans);
    return 0;
}

有任何疑问欢迎评论哦虽然我真的很菜