P5666 [CSP-S2019] 树的重心 - Solution
strcmp
·
·
题解
谷友们圣诞节快乐。
進んで 未来は
そこにあるから
可爱小南梁的几大特征，如果您的朋友有以下表现，那么她很可能是可爱的小南梁：
-
说话奶声奶气，喜欢喵喵叫。
-
喜欢粉白蓝配色。
-
喜欢穿可爱的女装。
-
不知道 dfs 序排行 \lceil\frac{n}{2}\rceil 的点的祖先链包含重心。
-
写这道题不给答案开 long long。
\Large\text{Main Text}
提供一个题解区没有的新做法，是模拟赛学到的一个 trick，感觉扩展性极高且对比其它做法思维上压倒性简单，就来分享一下。
重心的判定是 \max(n - \text{siz}_u,\,\text{siz}_{\text{maxson}}) 最小的点。
等价描述是重心的子树内一定包含 dfs 序排行 $\lceil\frac{n}{2}\rceil$ 的点。
**证明：**
**引理：** 以树的重心为根时，所有子树的大小不超过整棵树大小的一半。
证明根据重心的定义，重心是最大子树最小的点，如果有超过整棵树大小一半的子树，那重心往这个方向靠一定变优，矛盾。
也就是以任意点为根时，$n - \text{siz}_u \le \lfloor \frac{n}{2} \rfloor$，也即 $\text{siz}_u \ge \lceil\frac{n}{2}\rceil$。
重心 $u$ 的子树是区间 $[\text{dfn}_u,\,\text{dfn}_u + \text{siz}_u - 1]$，由区间长度 $\text{siz}_u \ge \lceil\frac{n}{2}\rceil$，必然包含 dfs 序排行 $\lceil\frac{n}{2}\rceil$ 的那个点。
---
知道这个结论之后这题就秒杀完了。
先钦定 $1$ 为根。
直接枚举删哪条边 $(u,\,\text{fa}_{u})$，整棵树分割成了 $u$ 子树和整棵树去掉 $u$ 子树后的联通块（显然也是一棵树）。
众所周知，$u$ 子树在 dfs 序上是一段区间 $[\text{dfn}_u,\,\text{dfn}_u + \text{siz}_u - 1]$。
首先 $u$ 这个子树的重心非常好找，我们直接维护 $\text{siz}$ 然后顺着重链用个指针扫下去即可，毕竟重心在重链上有单调性。
整棵树刨去 $u$ 子树怎么求？首先我们还是容易找到整棵树刨去 $u$ 子树的情况下，dfs 序排行一半的点是啥。
删去 $u$ 子树等价于 $\text{fa}_u$ 到根的路径的所有点的 $\text{siz}$ 全部减去 $\text{siz}_u$。
然后倍增，但是我们要单点查 $\text{siz}$ 是什么。
到根的链减和单点查，差分一下就是单点修改和子树查询，简单树状数组即可。同时维护重儿子和次重儿子，知道了 $\text{siz}$ 之后容易 check。
时间复杂度 $\Theta(n \log^2 n)$，有办法能直接优化到 $\Theta(\frac{n \log^2 n}{\log \log n})$ 但没有必要。
虽然对比其它做法时间复杂度上比较劣势，但**很容易**就能扩展到删去 $k$ 个子树求重心（直接维护前 $k$ 重儿子即可），而且完全不依赖本题要删除每个子树这个性质，可以直接做 $q$ 次询问。代码的话因为不需要啥思考很容易写，时间常数也比较小。甚至改一改也许能上 ETT 支持对树结构的修改（？）。
---
不对啊我在干什么。
实际上因为这题我们只有一个 $u$，因此每个点的 $\text{siz}$ 是完全可以简单 $\Theta(1)$ 求出的，那就是 $u$ 和 dfs 序排行一半的那个点的 LCA 之上 $\text{siz}$ 会减少 $\text{siz}_u$，于是你写一个 LCA 然后特判一点点东西即可。
时间复杂度 $\Theta(n \log n)$，思维难度压倒性的简单。
更进一步的，维护一些单调性感觉可以做到 $\Theta(n)$。比如考虑枚举 dfs 排行一半的点之类。留给读者思考。
这里给出 $\Theta(n \log n)$ 的代码。
月亮好闪，拜谢月亮。
```cpp
#include <bits/stdc++.h>
#define X first
#define Y second
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define per(i, a, b) for (int i = a; i >= b; i--)
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long int ll;
using ull = unsigned long long int;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pq = priority_queue<int>;
using ld = double;
constexpr int maxn = 3e5 + 10, mod = 1e9 + 7;
struct edge { int to, nxt; } nd[maxn << 1]; int h[maxn], cnt = 0;
inline void add(int u, int v) { nd[cnt].nxt = h[u], nd[cnt].to = v, h[u] = cnt++; }
int dfn[maxn], id[maxn], dct = 0, d[maxn], fa[maxn][20], sz[maxn], son[maxn], son2[maxn], n, T;
int p[maxn]; ll ans = 0; //p[i] 代表进入了 i 的哪个儿子，这样方便我们判定重儿子是否需要换，这里用到了题目直接遍历树的特殊性，但实际上再写个倍增就可以不用这个性质。
void dfs(int u, int f) {
fa[id[dfn[u] = ++dct] = u][0] = f; sz[u] = 1; son[u] = son2[u] = 0;
rep(i, 1, 19) fa[u][i] = fa[fa[u][i - 1]][i - 1];
for (int i = h[u]; ~i; i = nd[i].nxt) {
int v = nd[i].to;
if (v != f) {
dfs(v, u), sz[u] += sz[v];
if (sz[son[u]] < sz[v]) son2[u] = son[u], son[u] = v;
else if (sz[son2[u]] < sz[v]) son2[u] = v;
}
}
}
void dfs2(int u) {
int w = u;
for (int x = u; x; x = son[x]) {
//求出 x 为根子树的重心
auto D = [&](int v) { if (v == 0) return n; return max(sz[x] - sz[v], sz[son[v]]); };
while (son[w] && sz[son[w]] > sz[x] - sz[w]) w = son[w];
int mi = min({ D(fa[w][0]), D(w), D(son[w]) });
if (x != 1) {
if (D(fa[w][0]) == mi) ans += fa[w][0];
if (D(w) == mi) ans += w;
if (D(son[w]) == mi) ans += son[w];
}
for (int i = h[x]; ~i; i = nd[i].nxt) {
int v = nd[i].to;
if (v != son[x] && v != fa[x][0]) dfs2(v);
}
}
}
inline int lca(int u, int v) {
if (d[u] < d[v]) swap(u, v);
rep(i, 0, 19) if (d[u] - d[v] >> i & 1) u = fa[u][i];
if (u == v) return u;
per(i, 19, 0) if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
return fa[u][0];
}
void calc(int u) {
if (u == 1) return;
int L = dfn[u] - 1, R = n - dfn[u] - sz[u] + 1, x = (L + R + 1) / 2;
if (L < R) x -= L, x = id[dfn[u] + sz[u] + x - 1];
else x = id[x]; int w = lca(x, u); //求出 dfn 排行一半的点和 u 跟它的 lca
auto S = [&](int v) {
//此时的 maxson[v] 的 siz
if (d[v] > d[w] || p[v] != son[v]) return sz[son[v]];
else return sz[son[v]] - sz[u] > sz[son2[v]] ? sz[son[v]] - sz[u] : sz[son2[v]];
};
auto rl = [&](int v) {
if (d[v] > d[w] || p[v] != son[v]) return son[v];
else return sz[son[v]] - sz[u] > sz[son2[v]] ? son[v] : son2[v];
};
auto D = [&](int v) {
if (v == 0) return n;
return max(S(v), n - sz[v] - (!p[v] ? sz[u] : 0));
};
for (int i = 19; i >= 0; i--) {
int v = fa[x][i];
if (v && S(v) <= n - sz[v] - (!p[v] ? sz[u] : 0)) x = v;
}
//cout << S(1) << " " << n - sz[v] - (!p[v] ? sz[u] : 0) << "\n";
if (D(fa[x][0]) < D(x)) x = fa[x][0];
if (rl(x)) x = rl(x);
int mi = min({ D(x), D(fa[x][0]), D(fa[x][1]) });
//cout << u << " : " << ans << "\n";
if (D(x) == mi) ans += x; if (D(fa[x][0]) == mi) ans += fa[x][0]; if (D(fa[x][1]) == mi) ans += fa[x][1];
//cout << u << " : " << ans << "\n";
}
void dfs3(int u, int f) {
p[f] = u; calc(u);
for (int i = h[u]; ~i; i = nd[i].nxt) {
int v = nd[i].to;
if (v != f) dfs3(v, u);
}
p[u] = 0;
}
void solve() {
memset(h, -1, sizeof(h)); cnt = dct = ans = 0; scanf("%d", &n);
for (int i = 1, u, v; i < n; i++) scanf("%d%d", &u, &v), add(u, v), add(v, u);
dfs(1, 0); dfs2(1); dfs3(1, 0);
printf("%lld\n", ans);
}
int main() {
//freopen("centroid.in", "r", stdin);
//freopen("centroid.out", "w", stdout);
scanf("%d", &T);
while (T--) solve();
return 0;
}
```