洛谷5536 【XR-3】核心城市

题意

给出一棵 $n(\le 10^5)$ 个点的树，要求选连续的 $k$ 个点，使得其它城市到这些点距离的最大值最小。

题解

可以发现树的中心一定要选，然后中心的周围再选 $k-1$ 个点。

先求出直径，然后找到中心。再以中心为根，找到所有节点到叶节点的距离 $res[i]$ 并从大到小排序，然后选前 $k$ 个节点即可。

可以证明这些节点一定是连续的。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

const int N=100005;
struct Edge {
    int next,to;
} edge[N<<1];
int cnt,head[N],n,m,a,b,mx,mxi,fa[N],deep[N],maxd[N],res[N];

inline void add(int u,int v)
{
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

void dfs(int x,int f,int dep)
{
    fa[x]=f;
    if (dep>mx) mx=dep,mxi=x;
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (y==f) continue;
        dfs(y,x,dep+1);
    }
}

void dfs2(int x,int f,int dep)
{
    deep[x]=dep;
    maxd[x]=deep[x];
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (y==f) continue;
        dfs2(y,x,dep+1);
        maxd[x]=max(maxd[x],maxd[y]);
    }
    res[x]=maxd[x]-deep[x]+1;
}

signed main()
{
    n=read(); m=read();
    for (int i=1;i<n;i++)
    {
        a=read(); b=read();
        add(a,b);
        add(b,a);
    }
    dfs(1,0,0);
    int rt=mxi; mx=0;
    dfs(rt,0,0);
    rt=mxi; int tot=mx>>1;
    for (;tot;tot--) rt=fa[rt];
    dfs2(rt,0,0);
    sort(res+1,res+n+1);
    return !printf("%d",res[n-m]);
}