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

· · 题解

update 2020.10.04

更新图片

————————————————————

树的直径板子题

QwQ大佬的题解我都看不懂啊

所以自己发一篇吧

树的直径

树的直径有两种方法

树形DP求树的直径

void dp(int x,int fa){//x表示当前的节点，fa是x
的父节点
    for(int i=head[x];i;i=next[i]){//前向星
        int y=ver[i],z=w[i];//y是下一个节点，z是x，y的距离，在本题就是1
        if(y==fa)continue;//只用遍历一次，不用回到父节点
        dp(y);
        ans=max(ans,dis[x]+dis[y]+z);
        dis[x]=max(dis[x],dis[y]+z);
        //dis[x]表示从节点x出发走到以x为根的子树
        //能够到的最远距离
    }
}

树形DP难以求出直径上的节点

反正我不会QwQ

顺便提供几道树形DP的题目

P1352 没有上司的舞会

P1273 有线电视网

P2014 选课

两次DFS求树的直径

其实两次BFS也可以，这里介绍DFS的

第一次DFS我们从任意一个节点开始走

记录下离它最远的节点

它就是直径的一端了

为什么呢

我们假设它不是直径一端上的点

可是这样就违背了直径的定义

直径是树的最长链

如果它不是直径一端上的节点

那么就肯定会有一条比直径更长的链

所以不成立

证毕

然后用这个点再一次DFS，记录下路径就ok

void dfs1(int x,int fa){
    if(deep[x]>zj){
        zj=deep[x];
        num=x;
    }
    for(int i=head[x];i;i=next[i]){
        int y=ver[i];
        if(y==fa)continue;
        deep[y]=deep[x]+1;
        dfs1(y,x);
    }
}
void dfs2(int x,int fa){
    if(deep[x]>zj){
        zj=deep[x];
        num=x;
    }
    for(int i=head[x];i;i=next[i]){
        int y=ver[i];
        if(y==fa)continue;
        deep[y]=deep[x]+1;
        f[y]=x;//记录路径，表示y的父节点为x
        dfs2(y,x);
    }
}

然后我们来看题意

这 kk 座城市可以通过道路，在不经过其他城市的情况下两两相互到达

定义某个非核心城市与这k座核心城市的距离为，这座城市与k座核心城市的距离的最小值。那么所有非核心城市中，与核心城市的距离最大的城市，其与核心城市的距离最小。你需要求出这个最小值。

显然，k座城市的核心城市为直径中间那个城市

然后用这个城市向下搜就ok辽

用样例解释下

这是已经找了直径中点1的树

黑色是deep，表示树的深度

绿色表示maxdeep，表示这个点可以到达的最深的深度

对于节点x，离他最远的节点相距显然为maxdeep[x]-deep[x]

显然k座城市要取上面的

即maxdeep[x]-deep[x]前k大的

排序一下

那么剩下最大距离的最小值就一个一个比较就好了

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
#define N 100010
int n,k,zj,num,ans_k;
int cut,head[N],ver[2*N],next[2*N];
int deep[N],f[N],maxdeep[N],ans[N];
bool cmp(int a,int b){
    return a>b;
}
void add(int x,int y){
    ver[++cut]=y;next[cut]=head[x];head[x]=cut;
}
//求直径
void dfs1(int x,int fa){
    if(deep[x]>zj){
        zj=deep[x];
        num=x;
    }
    for(int i=head[x];i;i=next[i]){
        int y=ver[i];
        if(y==fa)continue;
        deep[y]=deep[x]+1;
        dfs1(y,x);
    }
}
void dfs2(int x,int fa){
    if(deep[x]>zj){
        zj=deep[x];
        num=x;
    }
    for(int i=head[x];i;i=next[i]){
        int y=ver[i];
        if(y==fa)continue;
        deep[y]=deep[x]+1;
        f[y]=x;
        dfs2(y,x);
    }
}
//
void dfs_k(int x,int fa){
    maxdeep[x]=deep[x];
    for(int i=head[x];i;i=next[i]){
        int y=ver[i];
        if(y==fa)continue;
        deep[y]=deep[x]+1;
        dfs_k(y,x);
        maxdeep[x]=max(maxdeep[x],maxdeep[y]);
    }
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<n;++i){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    //直径
    dfs1(1,0);
    memset(deep,0,sizeof(deep));
    zj=0;
    dfs2(num,0);
    //
    int kkk=num;
    //找直径的中点
    for(int i=1;i<=(deep[num]+1)/2;++i)kkk=f[kkk];
    memset(deep,0,sizeof(deep));
    //再搜一次
    dfs_k(kkk,0);
    for(int i=1;i<=n;++i)ans[i]=maxdeep[i]-deep[i];
    sort(ans+1,ans+n+1,cmp);
    //QwQ结合图片不难想
    for(int i=k+1;i<=n;++i)ans_k=max(ans_k,ans[i]+1);
    printf("%d\n",ans_k);
    return 0;
}

再来几道树的直径的题目吧

P1099 树网的核

P3629 [APIO2010]巡逻

P2195 HXY造公园

QwQ加一个题单吧

一个动态更新的洛谷综合题单