树的重心 题解

题目分析

这道题要求计算树中删除每条边后，两个连通分量的重心编号和之和。

关键点：

• 重心定义：删除节点后所有子树大小不超过⌊n/2⌋
• 需要处理所有边的删除情况
• 大规模数据（n最大299995）

解题思路

核心观察

1. 重心性质：树的重心是使得最大子树最小的节点
2. 双重心情况：当有两个重心时，它们的编号都要计入答案
3. 树链剖分：利用重链剖分优化查询

算法设计

代码采用了树链剖分 + 线段树 + 重心性质分析的方法：

主要步骤：

1. 预处理：树链剖分，计算子树大小
2. 线段树维护：维护DFS序上的子树大小信息
3. 重心查找：利用线段树快速查找重心
4. 分类计算：分别处理删除边后两个连通分量的重心

代码详解

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;

int T, n;
vector<int> E[N];
int fa[N], dfn[N], siz[N], reid[N];
long long ans;

// 线段树部分：维护子树大小信息
namespace SGT {
    struct node {
        int mx;  // 最大值
        int tag; // 懒标记
    } tr[N << 2];
    
    void build(int u = 1, int l = 1, int r = n) {
        tag(u) = 0;
        if (l == r) {
            mx(u) = siz[reid[l]];  // 存储子树大小
            return;
        }
        build(ls, l, mid);
        build(rs, mid + 1, r);
        pushup(u);
    }
    
    // 区间更新
    void update(int _ql, int _qr, int _val) {
        ql = _ql, qr = _qr;
        val = _val;
        upd();
    }
    
    // 查询满足条件的最小位置
    pii query(int ql, int qr, int lim) {
        flag = 0;
        res = {-1, -1};
        return qry(ql, qr, lim), res;
    }
}

// 树链剖分部分
namespace Tree {
    int son[N], top[N], cur;
    
    // 第一次DFS：计算子树大小和重儿子
    void dfs_pre(int u) {
        siz[u] = 1;
        for (int v : E[u]) {
            if (v == fa[u]) continue;
            fa[v] = u;
            dfs_pre(v);
            siz[u] += siz[v];
            if (siz[v] > siz[son[u]]) 
                son[u] = v;
        }
    }
    
    // 第二次DFS：树链剖分
    void dfs_path(int u, int tp) {
        top[u] = tp;
        dfn[u] = ++cur;
        reid[cur] = u;
        
        if (son[u]) dfs_path(son[u], tp);
        for (int v : E[u]) {
            if (v != fa[u] && v != son[u])
                dfs_path(v, v);
        }
    }
    
    // 计算删除边后u所在连通分量的重心和
    int solve1(int u) {
        // 在u的子树中查找重心
        auto [x, y] = SGT::query(dfn[u], dfn[u] + siz[u] - 1, (siz[u] + 1) / 2);
        
        // 处理双重心情况
        if (x == siz[u] / 2 && siz[u] % 2 == 0)
            return y + fa[y];
        return y;
    }
    
    // 计算删除边后另一个连通分量的重心和
    int solve2(int u) {
        int v = u, res = 0;
        
        // 临时修改子树大小（模拟删除边）
        while (top[v]) {
            SGT::update(dfn[top[v]], dfn[v], -siz[u]);
            v = fa[top[v]];
        }
        
        // 在剩余部分查找重心
        int l = dfn[u], r = dfn[u] + siz[u] - 1;
        
        // 检查右侧区间
        if (r < n) {
            auto [x, y] = SGT::query(r + 1, n, (n - siz[u] + 1) / 2);
            if (y != -1) {
                res += y;
                if (x == (n - siz[u]) / 2 && (n - siz[u]) % 2 == 0)
                    res += fa[y];
            }
        }
        
        // 检查左侧区间
        if (!res && 1 < l) {
            auto [x, y] = SGT::query(1, l - 1, (n - siz[u] + 1) / 2);
            res += y;
            if (x == (n - siz[u]) / 2 && (n - siz[u]) % 2 == 0)
                res += fa[y];
        }
        
        // 恢复修改
        v = u;
        while (top[v]) {
            SGT::update(dfn[top[v]], dfn[v], siz[u]);
            v = fa[top[v]];
        }
        
        return res;
    }
}

void Mysolve() {
    cin >> n;
    
    // 读入树结构
    for (int i = 1, x, y; i < n; ++i) {
        cin >> x >> y;
        E[x].push_back(y);
        E[y].push_back(x);
    }
    
    // 预处理
    Tree::dfs_pre(1);
    Tree::dfs_path(1, 1);
    SGT::build(1, 1, n);
    
    // 计算答案
    for (int i = 2; i <= n; ++i)
        ans += Tree::solve1(i);  // u所在连通分量
    
    for (int i = 2; i <= n; ++i)
        ans += Tree::solve2(i);  // v所在连通分量
    
    cout << ans << '\n';
    
    // 清空数据
    for (int i = 1; i <= n; ++i) E[i].clear();
    for (int i = 1; i <= n; ++i) Tree::son[i] = 0;
    ans = Tree::cur = 0;
}

int main() {
    freopen("centroid.in", "r", stdin);
    freopen("centroid.out", "w", stdout);
    cin >> T;
    while (T--) Mysolve();
    return 0;
}

算法原理详解

1. 重心查找原理

对于大小为n的树，重心是满足最大子树大小 ≤ n/2 的节点。

查找方法：

• 从根开始，每次走向大小 > n/2 的子树
• 最终找到的节点就是重心

2. 线段树作用

线段树维护DFS序上的子树大小，支持：

• 区间查询最大值
• 区间修改（模拟删除边的影响）

3. 双重心处理

当n为偶数且存在大小为n/2的子树时，有两个重心：

• 当前节点和其父节点
• 需要将两个重心编号都加入答案

4. 删除边的影响

删除边(u,v)后：

• u所在连通分量：大小siz[u]
• v所在连通分量：大小n - siz[u]

分别计算两个连通分量的重心。

复杂度分析

• 时间复杂度：O(n log n)，每个节点处理时间O(log n)
• 空间复杂度：O(n)，存储树结构和线段树

样例解析

以第一个样例为例：

5
1 2
2 3  
2 4
3 5

删除边(1,2)：

• 连通分量1：节点1，重心{1}
• 连通分量2：节点2,3,4,5，重心{2,3}

删除边(2,3)：

• 连通分量1：节点2,4，重心{2}
• 连通分量2：节点3,5，重心{3,5}

最终答案：1+2+3 + 2+3+5 + ... = 32

关键技巧

1. 树链剖分：将树转化为序列问题
2. 线段树优化：快速查询和修改子树信息
3. 临时修改：模拟删除边的影响
4. 双重心处理：正确处理偶数大小的情况

总结

这道题的解题亮点：

1. 问题分解：将复杂问题分解为独立的子问题
2. 数据结构应用：结合树链剖分和线段树高效处理
3. 重心性质利用：充分利用重心的数学性质
4. 工程实现：处理了多组数据和大规模情况

算法通过深入分析树的性质和巧妙的数据结构设计，在O(n log n)时间内解决了这个复杂的树论问题，展示了处理树上查询问题的高级技巧。