[Leaf] [P5536] 核心城市

p5536-【xr-3】核心城市---洛谷">P5536 【XR-3】核心城市 - 洛谷

1. 题面梗概

中译中：在一棵树上选 $k$ 个互相连接的点作为“核心城市”，使得剩下的城市到这 $k$ 个城市的最大距离最小。

2. 逻辑推导

直觉上，这看起来像一个树上的直径问题，或者说是几何中心？

如果 $k = 1$ 的话，我们发现，这个点应该就在直径路径上的中点。

当 $k > 1$ 时，为了保证核心城市群连通且依然保持 最远距离最小，我们必然以直径中点为根，向那些最深的支路进行扩张。

2.1 扩张

首先，每个节点 $u$ 的贡献，取决于它到其子树中最远叶子节点的距离 $dep[u]$。

所以如果一个点 $u$ 被选中，那么它的 $fa[u]$ 为了保证连通性必然被选中。

2.2 贪心

注意到 祖先的 dep 值必然大于 子树的 dep 值。

那么我们可以从最大的 dep 开始选，直接选前 $k$ 个节点作为核心城市。

2.3 二分

其实这种 最大距离最小 的题设，刻在DNA里的直觉告诉我应该使用二分答案。

我们可以 二分答案 $mid$，如果一个点到叶子的最远距离 $dep[u] \geq mid$，则说明它必须被选为核心城市。

然后 check 一下点数够不够 $k$ 个就行。

2.4 结论

这题的本质是利用直径的中心定位。

3. 代码实现

▶

AcCode

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

const int maxn = 1e5 + 50;

vector< int > adj[maxn];
int dist[maxn], fa[maxn];
int dep[maxn];
int n, k, ed;

void dfs( int u, int p, int d )
{
    dist[u] = d;
    fa[u] = p;
    if( dist[u] > dist[ed] ) ed = u;
    for( int v : adj[u] ) if( v != p ) dfs( v, u, d + 1 );
}

void dfs1( int u, int p )
{
    dep[u] = 0;
    for( int v : adj[u] )
    {
        if( v == p ) continue;
        dfs1( v, u );
        dep[u] = max( dep[u], dep[v] + 1 );
    }
}

bool check( int mid )
{
    int cnt = 0;
    for( int i = 1; i <= n; ++ i )
    {
        if( dep[i] >= mid ) cnt ++;
    }
    return cnt <= k;
}

void solve( )
{
    cin >> n >> k;
    for( int i = 1; i < n; ++ i )
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back( v );
        adj[v].push_back( u );
    }

    ed = 0, dist[0] = -1;
    dfs( 1, 0, 0 );
    int u = ed;
    ed = 0, dist[0] = -1;
    dfs( u, 0, 0 );
    int v = ed;

    vector< int > paths;
    for( int cur = v; cur != 0; cur = fa[cur] )
    {
        paths.push_back( cur );
    }
    int pos = paths[paths.size( ) / 2];

    dfs1( pos, 0 );

    int l = 0, r = n, ans = n;
    while( l <= r )
    {
        int mid = ( l + r ) >> 1;
        if( check( mid ) ) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    cout << ans << '\n';
}

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

4. 复盘

• 复杂度分析：二分和贪心都是 $O( N \log N )$。

• 碎碎念：直径练习的好题，类似板子题吧（bushi

• 关联笔记：直径与重心 | 浅谈二分答案 | 贪心策略