Luogu5666 [CSP-S2019] 树的重心（加强版）

发表于 更新于 分类于 ， ， 阅读次数：

题意：给出一棵 个节点的数， 次询问，每次询问给出 条边和 ，你需要列出在删除这 条边后， 所在连通块的所有重心坐标。

，。

  • 重心的性质1：记 的子树大小为 ， 的点形成一条链（一端是根），其最深的点 就是重心。若 ，那么 也是重心，否则没有第二个重心。

    证明：重心的充要条件：所有分支的大小都小于等于 。

    • 点 ：所有儿子子树大小都小于 ，向上的分支大小等于 减子树大小，也小于等于 。故 是重心。
    • 的祖先：若 ，易知 也是重心，否则不是。对于更浅的点，它们一定有一个儿子子树大小大于 ，故不是重心。

  • 重心的性质2：将 个节点按照 dfs 序排序，排在第 位的一定是重心的子孙。

    证明：重心的子树在 dfs 序中是一个区间，且长度 。它几乎一定覆盖中位数。

    只有一种特殊情形： 是偶数，区间长度恰为 ，此时区间可能在最前和最后，两者无交集。但稍微考虑就能发现，排第一的是根，若区间在最前面，包含了根，则一定包含整棵树。这说明略靠后的中位数—— 位，一定可以覆盖到。

删 条边得到的连通块由 个 dfs 序区间组成，具体地，记删除了 的父边：

  • 先找出 的最近祖先 ，将连通块初始化为 的子树（一个区间）；
  • 若 不是 的子孙，什么也不做；
  • 若 是 的子孙，从连通块中删除 的子树（一个区间）

可以 暴力完成。

考虑如下算法：

  • 先找出重心的一个子孙；
  • 向上倍增，找到第一个子树过半的节点，就是重心。

这要求对连通块能找 dfs 序中位数，能统计子树大小（和一个 dfs 序区间的交集大小），这些都可以 完成。

总复杂度 。

下面给出原题的代码：

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <cstdio>
#include <vector>

const int MaxN = 300050, MaxK = 20;

struct Solver {

std::vector<int> g[MaxN];
int f[MaxK][MaxN], in[MaxN], out[MaxN], id[MaxN], tim;
void dfs(int u) {
    id[in[u] = ++tim] = u;
    for (int v : g[u])
        if (!in[v]) {
        	f[0][v] = u;
            dfs(v);
        }
    out[u] = tim;
}

struct Segment {int l,r;};

int total(const std::vector<Segment> &l) {
	int sum = 0;
	for (const Segment &l0 : l)
		sum += l0.r-l0.l+1;
	return sum;
}
int kth(int k, const std::vector<Segment> &l) {
	for (const Segment &l0 : l) {
		int len = l0.r-l0.l+1;
		if (k>len) k-=len;
		else return l0.l+k-1;
	}
	return -1;
}
int subTreeSize(int u, const std::vector<Segment> &l) {
	int siz = 0;
	for (const Segment &l0 : l) {
		int L = std::max(in[u], l0.l),
			R = std::min(out[u], l0.r);
		siz += std::max(R-L+1, 0);
	}
	return siz;
}

int K;
int getCenter(int u, int S, const std::vector<Segment> &l) {
	if (2*subTreeSize(u, l) >= S)
		return u;
	for (int k=K; k>=0; k--)
		if (f[k][u] && 2*subTreeSize(f[k][u], l) < S)
			u = f[k][u];
	return f[0][u];
}
int calc(const std::vector<Segment> &l) {
	int S = total(l),
		mid = kth(S/2+1, l),
		t = id[mid], // dfs序中位数一定是重心的子孙 
		cent = getCenter(t, S, l);
	if (2*subTreeSize(cent, l) < S)
		puts("!");
	return (2*subTreeSize(cent, l) == S) ? 
		cent + f[0][cent] : // 双重心 
		cent;
}

void solve() {
	int N;
    scanf("%d", &N);
    while((1<<(K+1))<N) K++;
    for (int i=1; i<N; i++) {
        int u, v;
	    scanf("%d%d", &u, &v);
	    g[u].push_back(v);
	    g[v].push_back(u);
    }
    
    dfs(1);
    for (int k=1; k<=K; k++)
    	for (int u=1; u<=N; u++)
    		f[k][u] = f[k-1][f[k-1][u]];
    
    long long sum = 0;
    std::vector<Segment> l;
    for (int u=2; u<=N; u++) {
    	// 断开 u, fa[u] 之间的边
    	l.clear();
		l.push_back((Segment){in[u], out[u]});
		sum += calc(l);
		
		l.clear();
		l.push_back((Segment){1,in[u]-1});
		l.push_back((Segment){out[u]+1,N});
		sum += calc(l);
	}
	printf("%lld\n", sum);
}

}solver;

int main()
{
    int T;
    scanf("%d", &T);
    while(T--) {
    	solver = Solver();
    	solver.solve();
	}
    return 0;
}