题解 P5536【XR-3】核心城市

· · 题解

题目传送门

前置知识

树的直径定义： 我们将一棵树T = ( V，E )的直径定义为maxδ ( u，v ) ( u，v ∈ V )，也就是说，树中所有最短路径距离的最大值即为树的直径。

做法：

1. 两次dfs(或bfs)

先从任意一点P出发，找离它最远的点Q，再从点Q出发，找离它最远的点W，W到Q的距离就是是的直径。

2. 树形DP

对于每个节点我们要记录两个值：

f1[i] 表示以 i 为根的子树中，i 到叶子结点距离的最大值

f2[i] 表示以 i 为根的子树中，i 到叶子结点距离的次大值

对于一个节点，它到叶子结点距离的最大值和次大致所经过的路径肯定是不一样的

若j是i的儿子，那么（下面的 w [ i ][ j ] 表示 i 到 j 的路径长度）：

若 f1 [ i ] < f1 [ j ] + w [ i ][ j ]，f2 [ i ] = f1 [ i ]，f1 [ i ] = f1 [ j ] + w [ i ][ j ]；

否则，若 f2 [ i ] < f1 [ j ] + w [ i ][ j ]，f2 [ i ] = f1 [ j ] + w [ i ][ j ]；

题目大意：

找到一种选点的方法，使得所有非核心城市中离核心城市的最大距离最小。

思路1：二分 但是我们能发现题目中的边权都为1，考虑其他算法。

若k=1，那么显然应该放在树的直径的中点处，k如果再加，就尽可能让答案小一些。 定义dep为深度，mdep为向下能到的最大深度，那么就把mdep-dep当做关键字从大到小排序，前k个可以放入核心城市 那么答案就是mdep[k+1]-dep[k+1]+1。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
const int N =5e5+1;
using namespace std;
int n,m,x,y,ru[N],f[N];
int dep[N],mdep[N],maxx,maxx2,zj1,zj2,root,ans[N];
int fir[N],nex[N<<1],poi[N<<1],w[N<<1],sum;
void add(int x,int y)
{
    nex[++sum]=fir[x];
    poi[sum]=y;
    fir[x]=sum;
}
void dfs(int x,int fa)
{
    dep[x]=dep[fa]+1;
    for(int i=fir[x];i;i=nex[i])
    {
        if(fa==poi[i]) continue;
        dfs(poi[i],x);
    }
}
void dfss(int x,int fa)
{
    mdep[x]=dep[x];
    for(int i=fir[x];i;i=nex[i])
    {
        int p=poi[i];
        if(fa==p) continue;
        dfss(p,x);
        mdep[x]=max(mdep[p],mdep[x]);
    }
}
void dfs_1(int x,int fa,int d)
{
    if(d>maxx)
    {
        zj1=x;
        maxx=d;
    }
    for(int i=fir[x];i;i=nex[i])
    {
        int p=poi[i];
        if(p==fa)  continue;
        dfs_1(p,x,d+1);
        f[poi[i]]=x;
    }
}
void dfs_2(int x,int fa,int d)
{
    if(d>maxx2)
    {
        zj2=x;
        maxx2=d;
    }
    for(int i=fir[x];i;i=nex[i])
    {
        int p=poi[i];
        if(p==fa) continue;
        dfs_2(p,x,d+1);
    }
}
bool cmp(int a,int b)
{
    return a>b;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n-1;i++)
    {
        int x,y,z;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    dfs_1(1,0,0);
    dfs_2(zj1,0,0);
    root=zj1;
    int pan=maxx2;
    for(int i=1;i<=(maxx2)/2;i++)
    root=f[root];   
    dfs(root,0);
    dfss(root,0);
    for(int i=1;i<=n;i++)
    ans[i]=mdep[i]-dep[i];
    sort(ans+1,ans+1+n,cmp);
    printf("%d\n",ans[m+1]+1);
}
/*
6 3
1 2
2 3
2 4
1 5
5 6*/