题意

给一棵 \(n\) 个点的树，求断掉每条边后两棵树的重心。输出编号和。\(n \leq 3\times 10 ^ 5\)。

题解

solution by hydd

显然任意情况下两个重心一定是相邻的，我们先求出其中较靠下的那个重心，最后 \(check\) 一下其父亲是不是也是重心就可以了。

结论：任意一个树，以任意点为根，重心（所有重心）一定在根所在的重链上。

我们选择一个重心作为树根。

接下来考虑每个点的子树的重心。令 \(f_i\) 表示 \(i\) 的子树的重心，\(w_i\) 表示 \(i\) 的重儿子。可以发现 \(f_i\) 一定是 \(f_{w_i}\) 的祖先，暴力跳就可以了（每条重链上都只会从下往上跳，所以总复杂度是 \(\mathcal O(n)\)）。

复杂的是求每个点子树外的重心。下面用 \(r\) 表示树根（也是全树的重心）。

如果某个点 \(x\) 不在 \(w_r\) 的子树里，那么删掉 \(x\) 的子树之后 \(r\) 的重儿子一定还是 \(w_r\)，从而重心还在原来那条重链上。把这条重链从上到下排列下来记作 \(p_1(=r),p_2(=w_r),…,p_k\)，那么删掉 \(x\) 的子树后，重心就是最靠下的点 \(p_i\) 使得 \(siz_{p_i}\geqslant\lceil \frac{n−siz_x}2\rceil\)。可以直接预处理出对每个 \(t\)，最靠下的 \(siz_{p_i}\geqslant t\) 的点是哪个，然后 \(\mathcal O(1)\) 查询。

还剩下 \(w_r\) 的子树里的那些点。记 \(v_r\) 表示 \(r\) 的次大的儿子，我们“假装”把根节点的重链转而连到 \(v_r\) 上；如果 \(x\) 是 \(w_r\) 的子树里的点，那么有两种可能：

1. 删掉 \(x\) 及其子树之后根节点的重儿子没变。但是这样的话既然本来重心就是 \(r\)，删掉 \(x\) 的子树显然不会使得重心反而往 \(x\) 的方向靠近。因此这时候重心还会是 \(r\)；
2. 删掉 \(x\) 的子树后根节点的重儿子变了，那显然会变成 \(v_r\)。于是重心会在 \(r\)，或者 \(v_r\) 的重链上。

总之我们可以假装把 \(r\) 的重儿子改成 \(v_r\)，然后对重儿子子树里所有的点做一个像之前求不在 \(w_r\) 子树里的点的答案一样的做法。

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

#include <bits/stdc++.h>

const int bufsize = (1 << 20) + 10, N = 3e5 + 10;

inline char Getchar()
{
    static char buf[bufsize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufsize, stdin), p1 == p2) ? EOF : *p1++;
}

inline int read()
{
    int x = 0;
    char ch = Getchar();
    while (!isdigit(ch)) ch = Getchar();
    while (isdigit(ch)) x = x * 10 + ch - '0', ch = Getchar();
    return x;
}

int tot = 1, fir[N], nex[N << 1], got[N << 1];

inline void AddEdge(int u, int v)
{
    nex[++tot] = fir[u], fir[u] = tot, got[tot] = v;
    nex[++tot] = fir[v], fir[v] = tot, got[tot] = u;
}

int rot = 0, siz[N], Max[N], son[N], par[N];
int idx = 0, dfn[N], b[N], w[N], p[N], a[N];

inline void dfs(int u, int fa, int n)
{
    siz[u] = 1, Max[u] = 0;
    for (int i = fir[u]; i; i = nex[i]) if (got[i] != fa) 
        dfs(got[i], u, n), siz[u] += siz[got[i]], Max[u] = std::max(Max[u], siz[got[i]]);
    Max[u] = std::max(Max[u], n - siz[u]);
    if (!rot || Max[u] < Max[rot]) rot = u;
}

inline void dfs(int u, int fa)
{
    siz[u] = 1, Max[u] = son[u] = 0, par[u] = fa, dfn[u] = ++idx;
    for (int i = fir[u]; i; i = nex[i]) if (got[i] != fa) 
    {
        dfs(got[i], u), siz[u] += siz[got[i]];
        Max[u] = std::max(Max[u], siz[got[i]]);
        if (siz[got[i]] > siz[son[u]]) son[u] = got[i];
    }
    if (siz[u] == 1) w[u] = u; else w[u] = w[son[u]];
    while (siz[u] - siz[w[u]] > siz[u] / 2) w[u] = par[w[u]];
}

int main()
{
    int T = read();
    while (T--)
    {
        memset(fir, 0, sizeof(fir)), tot = 1;
        int n = read(), now = 0, cnt = 0, s = 0, tmp = 0; long long ans = 0;
        for (int i = 1; i <= n - 1; ++i) AddEdge(read(), read());
        idx = rot = 0, dfs(1, 0, n), dfs(rot, 0);
        auto check = [&](int u, int v) {return Max[v] <= siz[u] / 2;};
        auto Check = [&](int u, int v) {return Max[v] <= (n - siz[u]) / 2;};
        for (int i = 1; i <= n; ++i) if (i != rot) ans += w[i] + check(i, par[w[i]]) * par[w[i]];
        for (int now = rot; now; now = son[now]) p[++cnt] = now; p[cnt + 1] = 0;
        for (int i = 1; i <= cnt; ++i) for (int j = siz[p[i + 1]] + 1; j <= siz[p[i]]; ++j) a[j] = p[i];
        for (int i = fir[rot]; i; i = nex[i]) if (got[i] != son[rot] && siz[got[i]] > siz[s]) s = got[i];
        cnt = 0, tmp = son[rot], son[rot] = s;
        for (int now = rot; now; now = son[now]) p[++cnt] = now; p[cnt + 1] = 0;
        for (int i = 1; i <= cnt; ++i) for (int j = siz[p[i + 1]] + 1; j <= siz[p[i]]; ++j) b[j] = p[i];
        for (int i = 1; i <= n; ++i)
        {
            if (i == rot) continue;
            int w = (n - siz[i]) / 2 + ((n - siz[i]) & 1);
            if (dfn[tmp] <= dfn[i] && dfn[i] < dfn[tmp] + siz[tmp])
            {
                ans += b[w] + (Check(i, par[b[w]]) || (par[b[w]] == rot && siz[s] <= (n - siz[i]) / 2)) * par[b[w]];
            }
            else ans += a[w] + Check(i, par[a[w]]) * par[a[w]];
        }
        printf("%lld\n", ans);
    }
    return 0;
}