[Leaf] [P5666] 树的重心

p5666-[csp-s-2019]-树的重心---洛谷">P5666 [CSP-S 2019] 树的重心 - 洛谷

1. 题面梗概

中译中：删掉树上的一条边，原本的树会断成两半。求这两半树各自重心的编号之和。
你需要把整棵树的所有边都试一遍，最后求一个总和。

2. 逻辑推导

很显然这题考的是树的重心的知识点。如果暴力删掉每一边，然后对两棵树跑一遍 DFS，复杂度很显然是 $O(N^2)$ 绝对会炸。

那么我们就得从重心的性质入手了。

2.1 重心

设 $u$ 节点的子树大小为 $sz[u]$。

我们明确一下重心的判定准则，若 $u$ 是重心，那么 $sz[u] \geq n / 2$ 且 $sz[max\_son[u]] \leq n / 2$。

所以当我们删掉一条边的时候，新树的重心 一定会向 原树重心的重儿子 方向上转移。

那我们不妨以原树的重心为根节点，重建一颗树，然后遍历每一条边，处理重心的新位置，因为 新重心 在 旧重心 的重儿子方向上，所以只需要跳转几次判断就行了。

2.2 倍增

因为节点很多，即便我们知道偏移方向是在重儿子上，但是由于节点数量太多了，特别是退化成链的极端情况，这个复杂度就很危险了。

考虑到是在重儿子上寻找路径，我们可以采用类似 求LCA 的倍增思路，提前预处理这条路径，从而实现 $O(\log N)$ 的查询。

但是这里有一个细节，如果删掉的边正好在 root 的重儿子分支上，那么 root 的重路径就需要转移到次重儿子上。

2.3 结论

这题是重心性质和倍增技巧的巧妙结合，理论上还有别的方法，不过我个人认为这个方法比较好理解，也是我能掌握的。

3. 代码实现

▶

AcCode

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 3e5 + 50;
const int maxlg = 20;

struct Edge { int u, v; };

vector< int > adj[maxn];
int sz[maxn], f[maxn];
int son1[maxn], son2[maxn];
int down[maxn][maxlg], fa[maxn];
int bel[maxn]; // belong 记录每个点属于根节点的哪个分支
int n, rt;
ll ans;

void get_root( int u, int p )
{
    sz[u] = 1;
    f[u] = 0;

    for( int v : adj[u] )
    {
        if( v == p ) continue;
        get_root( v, u );
        sz[u] += sz[v];
        f[u] = max( f[u], sz[v] );
    }

    f[u] = max( f[u], n - sz[u] );
    if( f[u] < f[rt] ) rt = u;
}

void dfs( int u, int p, int top )
{
    sz[u] = 1;
    fa[u] = p;
    bel[u] = top;
    son1[u] = son2[u] = 0;

    for( int v : adj[u] )
    {
        if( v == p ) continue;

        if( u == rt ) dfs( v, u, v );
        else dfs( v, u, top );
        sz[u] += sz[v];

        if( sz[v] > sz[son1[u]] ) son2[u] = son1[u], son1[u] = v;
        else if( sz[v] > sz[son2[u]] ) son2[u] = v;
    }
    down[u][0] = son1[u];
    for( int i = 1; i < maxlg; ++ i ) down[u][i] = down[down[u][i - 1]][i - 1];
}

// 检查 u 是否是当前大小为 sum 树的重心
int check( int u, int sum, int ms )
{
    return u * ( max( ms, sum - sz[u] ) <= sum / 2 );
}

// 寻找连通块的重心
void calc( int st, int sum, int del )
{

    int son = son1[st];
    // 如果重儿子被删了，切换到次重儿子
    if( st == rt && son1[st] == del ) son = son2[st];

	// 起点可能是重心
    ans += check( st, sum, sz[son] );
    
    if( son == 0 || sz[son] < ( sum + 1 ) / 2 ) return;

	// 沿重链下跳，找到满足条件的点
    int cur = son;
    for( int i = maxlg - 1; i >= 0; -- i )
    {
        int nxt = down[cur][i];
        if( nxt && sz[nxt] >= ( sum + 1 ) / 2 ) cur = nxt;
    }
	
	// 重心可能有两个且相邻，特判
    ans += check( cur, sum, sz[son1[cur]] );
    if( cur != son ) ans += check( fa[cur], sum, sz[son1[fa[cur]]] );
}

void solve( )
{
    cin >> n;

    ans = 0;
    for( int i = 1; i <= n; ++ i ) adj[i].clear( );

    vector< Edge > edges;
    for( int i = 1; i < n; ++ i )
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back( v );
        adj[v].push_back( u );
        edges.push_back( { u, v } );
    }

    rt = 0; f[0] = n + 1;
    get_root( 1, 0 );
    dfs( rt, 0, 0 );

    for( auto [u, v] : edges )
    {
        if( fa[v] != u ) swap( u, v );
        
        // 分别处理两个连通块
        calc( v, sz[v] , 0 );
        calc( rt, n -  sz[v], bel[v] );
    }

    cout << ans << '\n';
}

int main( )
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int T; cin >> T;
    while( T -- ) solve( );
    return 0;
}

4. 复盘

• 复杂度分析：$O( N \log N )$。两次 DFS 是 $O(N)$，枚举边并在重链上跳倍增是 $O(N \log N)$。

• 碎碎念：这题逻辑上其实不难理解，注意到重心会向着重儿子的方向偏移就好写了，同时考虑倍增优化复杂度就能过了。但是在具体代码实现上，这个逻辑分支就很麻烦。

• 关联笔记：直径与重心 | 倍增策略