Dyd's Blog

He who has a strong enough why can bear almost any how.

luoguP5666 [CSP-S2019] 树的重心

Posted on
Symbols count in article: 2.7k Reading time ≈ 2 mins.

重心 + 拆贡献 + BIT

树的重心

思路

一眼瞪过去估计要 $O(n \log n)$ ，枚举断边估计不行（其实是可以的， 打脸），考虑拆贡献，统计每个点可以做多少次重心

随便定一个根，设当前考虑的是点 $x$ ，记 $si[x]$ 表示 $x$ 的子树， $son[x]$ 表示重儿子，考虑合法的断边：

  • 若该断边在 $x$ 的子树外，记 $S$ 为断掉该边后 $x$ 不在的那棵树的大小，有 $n - S - si[x] \le \frac{n - S}{2}, si[son[x]] \le \frac{n - S}{2}$ ，即 $n - 2 * si[x] \le S \le n - 2 * si[son[x]]$

    如果不必考虑在 $x$ 的子树外，用一个 BIT 动态维护每个 $S$ 的个数，随 $x$ 的移动修改（把 $si[fa]$ 换成 $n - si[fa]$ ）即可；再用一 BIT 记录一下已经遍历的信息，那么遍历完 $x$ 的子树后该 BIT 的增加量就是多算的次数

  • 若断边在 $x$ 的子树内，发现不好做；考虑把整棵树的根定为树的重心，这样当 $x$ 不是根的时候，就可以避免这种情况（比较巧妙）

    而当 $x$ 是根的时候，记根的次重儿子为 $nxs$ ，那么对于树上非根节点 $y$ ，我们考虑断它与父亲的边：

    • 若 $y$ 不在 $son[rt]$ 的子树内，那么 $si[son[rt]] \le \frac{n - si[y]}{2}$ ，即 $si[y] \le n - 2 * si[son[rt]]$
    • 否则， $si[nxs] \le \frac{n - si[y]}{2}$ ，即 $si[y] \le n - 2 * si[nxs]$

总时间 $O(n \log n)$

另外好像有枚举断边， $O(\log n)$ 计算重心的做法，注意利用了一个性质：一棵树的重心一定在其根所在重链上，用类似换根的方法维护重链，每次在重链上倍增，复杂度一样

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
using LL = long long;
const int N = 3e5 + 100;
int n, h[N], idx;
int c[2][N];
int rt, si[N], son[N], nxs;
LL ans;
void cg(int id, int x, int d = 1){ for (++x; x <= n + 1; x += x & -x) c[id][x] += d; }
LL ask(int id, int x)
{
    LL res = 0;
    for (++x; x; x ^= x & -x) res += c[id][x];
    return res;
}
struct Edge{ int ne, ver; } e[N << 1];
void add(int x, int y){ e[idx] = {h[x], y}, h[x] = idx++; }
void dfs(int x, int fa)
{
    si[x] = 1, son[x] = 0;
    for (int i = h[x], y; ~i; i = e[i].ne) if ((y = e[i].ver) != fa)
    {
        dfs(y, x);
        si[x] += si[y];
        if (si[y] > si[son[x]]) son[x] = y;
    }
}
void calc(int x, int fa, bool is)
{
    cg(0, n - si[x]);
    if (x ^ rt)
    {
        ans += x * ask(0, n - (si[son[x]] << 1));
        ans -= x * ask(0, n - (si[x] << 1) - 1);
        ans += rt * (si[x] <= n - (si[is ? nxs : son[rt]] << 1));
        ans += x * ask(1, n - (si[son[x]] << 1));
        ans -= x * ask(1, n - (si[x] << 1) - 1);
    }
    cg(1, si[x]);
    cg(0, si[x], -1);
    for (int i = h[x], y; ~i; i = e[i].ne) if ((y = e[i].ver) != fa) calc(y, x, is || y == son[rt]);
    cg(0, si[x]);
    if (x ^ rt)
    {
        ans -= x * ask(1, n - (si[son[x]] << 1));
        ans += x * ask(1, n - (si[x] << 1) - 1);
    }
    cg(0, n - si[x], -1);
}
int main()
{
    freopen("centroid.in", "r", stdin);
    freopen("centroid.out", "w", stdout);
    int T;
    for (scanf("%d", &T); T--; )
    {
        scanf("%d", &n);
        std::memset(h, -1, (n + 1) << 2), idx = ans = nxs = 0;
        std::memset(c[0] + 1, 0, (n + 1) << 2);
        std::memset(c[1] + 1, 0, (n + 1) << 2);
        for (int i = 1, u, v; i < n; ++i)
        {
            scanf("%d %d", &u, &v);
            add(u, v), add(v, u);
        }
        dfs(1, -1), rt = 0;
        for (int i = 1; i <= n && !rt; ++i) if (n - si[i] <= (n >> 1) && si[son[i]] <= (n >> 1)) rt = i;
        dfs(rt, -1);
        for (int i = h[rt]; ~i; i = e[i].ne) if (e[i].ver != son[rt] && si[e[i].ver] > si[nxs]) nxs = e[i].ver; 
        for (int i = 1; i <= n; ++i) cg(0, si[i]);
        calc(rt, -1, false);
        printf("%lld\n", ans);
    }
    return 0;
}