专栏文章

P5666 [CSP-S2019] 树的重心 - Solution

sstrcmp
P5666题解参与者 11已保存评论 14

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
14 条
当前快照
1 份
快照标识符
@mir4ednx
此快照首次捕获于
2025/12/04 15:34
3 个月前
此快照最后确认于
2025/12/04 15:34
3 个月前
查看原文
谷友们圣诞节快乐。
  • 前言
進んで 未来は
そこにあるから
可爱小南梁的几大特征，如果您的朋友有以下表现，那么她很可能是可爱的小南梁：
  1. 说话奶声奶气，喜欢喵喵叫。
  2. 喜欢粉白蓝配色。
  3. 喜欢穿可爱的女装。
  4. 不知道 dfs 序排行 ⌈n2⌉\lceil\frac{n}{2}\rceil 的点的祖先链包含重心。
  5. 写这道题不给答案开 long long。
Main Text\Large\text{Main Text}
提供一个题解区没有的新做法，是模拟赛学到的一个 trick，感觉扩展性极高且对比其它做法思维上压倒性简单，就来分享一下。
重心的判定是 max⁡(n−sizu, sizmaxson)\max(n - \text{siz}_u,\,\text{siz}_{\text{maxson}}) 最小的点。
nn 个结点的树，任意定一个点为根，任意 dfs 序下排行 ⌈n2⌉\lceil\frac{n}{2}\rceil 的点的祖先链中一定包含重心。
等价描述是重心的子树内一定包含 dfs 序排行 ⌈n2⌉\lceil\frac{n}{2}\rceil 的点。
证明：
引理： 以树的重心为根时，所有子树的大小不超过整棵树大小的一半。
证明根据重心的定义，重心是最大子树最小的点，如果有超过整棵树大小一半的子树，那重心往这个方向靠一定变优，矛盾。
也就是以任意点为根时，n−sizu≤⌊n2⌋n - \text{siz}_u \le \lfloor \frac{n}{2} \rfloor，也即 sizu≥⌈n2⌉\text{siz}_u \ge \lceil\frac{n}{2}\rceil。
重心 uu 的子树是区间 [dfnu, dfnu+sizu−1][\text{dfn}_u,\,\text{dfn}_u + \text{siz}_u - 1]，由区间长度 sizu≥⌈n2⌉\text{siz}_u \ge \lceil\frac{n}{2}\rceil，必然包含 dfs 序排行 ⌈n2⌉\lceil\frac{n}{2}\rceil 的那个点。
知道这个结论之后这题就秒杀完了。
先钦定 11 为根。
直接枚举删哪条边 (u, fau)(u,\,\text{fa}_{u})，整棵树分割成了 uu 子树和整棵树去掉 uu 子树后的联通块（显然也是一棵树）。
众所周知，uu 子树在 dfs 序上是一段区间 [dfnu, dfnu+sizu−1][\text{dfn}_u,\,\text{dfn}_u + \text{siz}_u - 1]。
首先 uu 这个子树的重心非常好找，我们直接维护 siz\text{siz} 然后顺着重链用个指针扫下去即可，毕竟重心在重链上有单调性。
整棵树刨去 uu 子树怎么求？首先我们还是容易找到整棵树刨去 uu 子树的情况下，dfs 序排行一半的点是啥。
删去 uu 子树等价于 fau\text{fa}_u 到根的路径的所有点的 siz\text{siz} 全部减去 sizu\text{siz}_u。
然后倍增，但是我们要单点查 siz\text{siz} 是什么。
到根的链减和单点查，差分一下就是单点修改和子树查询，简单树状数组即可。同时维护重儿子和次重儿子，知道了 siz\text{siz} 之后容易 check。
时间复杂度 Θ(nlog⁡2n)\Theta(n \log^2 n)，有办法能直接优化到 Θ(nlog⁡2nlog⁡log⁡n)\Theta(\frac{n \log^2 n}{\log \log n}) 但没有必要。
虽然对比其它做法时间复杂度上比较劣势，但很容易就能扩展到删去 kk 个子树求重心（直接维护前 kk 重儿子即可），而且完全不依赖本题要删除每个子树这个性质，可以直接做 qq 次询问。代码的话因为不需要啥思考很容易写，时间常数也比较小。甚至改一改也许能上 ETT 支持对树结构的修改（？）。
不对啊我在干什么。
实际上因为这题我们只有一个 uu，因此每个点的 siz\text{siz} 是完全可以简单 Θ(1)\Theta(1) 求出的，那就是 uu 和 dfs 序排行一半的那个点的 LCA 之上 siz\text{siz} 会减少 sizu\text{siz}_u，于是你写一个 LCA 然后特判一点点东西即可。
时间复杂度 Θ(nlog⁡n)\Theta(n \log n)，思维难度压倒性的简单。
更进一步的，维护一些单调性感觉可以做到 Θ(n)\Theta(n)。比如考虑枚举 dfs 排行一半的点之类。留给读者思考。
这里给出 Θ(nlog⁡n)\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;
}

评论

共 14 条评论，欢迎与作者交流。

正在加载评论...