P5666 题解

· · 题解

第二篇题解的思路很好，但是过于简略了。

树的重心有一个性质：对于以 u 为根的一颗子树，如果 u 不是子树的重心，那么重心一定在 u 的重儿子里面。所以重心的方向是可以完全地确定的。

然后就类似 LCA，我们可以设 p_{i,k} 表示 i 沿着重儿子一直往下走了 2^k 次到达的结点。对于一颗子树，我们可以用 p 来在 O(\log n) 的时间复杂度内求出它的重心。具体地，我们在倍增的过程中，可以找到一个最深的重儿子 v，使得 s_v \ge \lceil\frac{s_u}{2}\rceil。那么 v 和它的父亲都是重心的“候选结点”，判断并更新答案即可。

关于实现，可以通过换根的方式，维护换根后每个结点的子树大小、父亲、重儿子。

时间复杂度 O(n \log n)。

#include <bits/stdc++.h>
using namespace std;
#define MAXN 300000
#define MAXK 19
#define judge(x, sum) (x) * (max(siz2[son3[x]], (sum)-siz2[x]) <= (sum >> 1))  // 判断是否为重心

int t, n, u, v;
int fa[MAXN], fa2[MAXN];  // 父亲
int siz[MAXN], siz2[MAXN];  // 子树大小
int son[MAXN], son2[MAXN], son3[MAXN];  // 重儿子、次重儿子
int p[MAXN][MAXK];
list<int> e[MAXN];
long long ans;

void clear(){
    ans = 0;
    memset(son, 0, sizeof(son));
    memset(p, 0, sizeof(p));
    for (int i(1); i<=n; ++i) e[i].clear();
}

void dfs1(int x, int f){
    siz[x] = 1;
    fa[x] = f;
    for (auto i: e[x]){
        if (i ^ f){
            dfs1(i, x);
            siz[x] += siz[i];
            if (siz[son[x]] < siz[i]){
                son2[x] = son[x];
                son[x] = i;
            }else if (siz[son2[x]] < siz[i]) son2[x] = i;
        }
    }
    p[x][0] = son[x];
    for (int i(1); i<MAXK; ++i) p[x][i] = p[p[x][i-1]][i-1];
}

void dfs2(int x){
    for (auto i: e[x]){
        if (i ^ fa[x]){
            siz2[x] = n - siz[i];
            fa2[x] = fa2[i] = 0;
            son3[x] = (son[x] == i ? son2[x] : son[x]);
            if (siz2[fa[x]] > siz2[son3[x]]) son3[x] = fa[x];

            p[x][0] = son3[x];
            for (int j(1); j<MAXK; ++j) p[x][j] = p[p[x][j-1]][j-1];

            int tmp(x);  // 求出 x 的重心
            for (int j(MAXK-1); j>=0; --j){
                if (siz2[p[tmp][j]] >= ((siz2[x]+1) >> 1)) tmp = p[tmp][j];
            }
            ans += judge(tmp, siz2[x]) + judge(fa2[tmp], siz2[x]);

            tmp = i;  // 求出 i 的重心
            for (int j(MAXK-1); j>=0; --j){
                if (siz2[p[tmp][j]] >= ((siz2[i]+1) >> 1)) tmp = p[tmp][j];
            }
            ans += judge(tmp, siz2[i]) + judge(fa2[tmp], siz2[i]);
            fa2[x] = i;
            dfs2(i);
        }
    }
    son3[x] = p[x][0] = son[x];
    for (int i(1); i<MAXK; ++i) p[x][i] = p[p[x][i-1]][i-1];
    fa2[x] = fa[x];
    siz2[x] = siz[x];
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> t;
    while (t--){
        cin >> n;
        clear();
        for (int i(1); i<n; ++i){
            cin >> u >> v;
            e[u].push_back(v);
            e[v].push_back(u);
        }
        dfs1(1, 0);

        memcpy(siz2, siz, sizeof(siz));
        memcpy(son3, son, sizeof(son));
        memcpy(fa2, fa, sizeof(fa2));
        dfs2(1);

        cout << ans << '\n';
    }

    return 0;
}