题解 P5536 【【XR-3】核心城市】
首先我们来看一下什么是树的直径,简单来说直径就是树中最长一条路径(不唯一)
至于求直径我这里是用@e_e_thinker大佬的方法,先从任意点搜索搜到的最远点位直径的一端,再重一段开始搜搜到的最远点即为另一端,再找完整路径就可以了
注意到最长路径,我们再看看题目要求我们使与核心城市的距离最大的城市，其与核心城市的距离最小
(注:下文如果出现类似一个点到多个点的距离,指一个点到多个点的距离中的最大值)
由于直径是最长的路径,我们可以先考虑解决它,那么我们首先来看那个点作为核心城市可以使直径的两端点到其的距离的较大值最小,不难知道是直径的中点(直径的中点,如果直径上有1~n号节点,n为奇数时,中点为(n+1)/2号,为偶数时为(n/2)号)
然后我们再来看其他点到中点的距离,由于直径的定义其他点到中点的距离一定不大于直径两端到中点的距离(因为如果大于,就一定能找到一条比直径更长的路径,如下图)
所以直径中点一定是核心城市(其他点到直径两端的大于直径中点),由题意得其他核心城市一定和中点相连,所以我们可以以中点为根建一颗有根树(代码中只是改变了搜索的起点罢了)
我们先来看题目中的一句话,定义某个非核心城市与这k座核心城市的距离为，这座城市与k座核心城市的距离的最小值。
warning:后面可能会有点绕,可以直接看结论加图食用
建树有什么用呢,一开始我们只确定了一个核心城市,就是直径的中点(根),由于核心城市都是相邻的,所以里核心城市最远的节点一定是叶子节点(可以画图看看),根据定义,且其到核心城市的距离一定是其到它第一个为核心城市的祖先节点的距离,由于树上路径长为1,所以距离也就是它的深度减一个为核心城市的祖先节点的深度
所以如果一个非核心城市他到它往下走到的叶子节点的距离很大,那么它一定要作为核心城市(如果不做,那个叶子节点到其他核心城市的距离更大)
所以得出结论
所以我们可以将每个非核心城市到可以到达的最深叶子节点的深度减其自身的深度的值
具体看代码吧
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;
int n,k,zj[N],yd,zjs,maxn,ryd,ft[N],nx[N],to[N],gx[N];//zj[i]为直径路径上i第i点,n,k看题目,yd为一端,ryd为另一端(lyd???),ft,nx,to建图,gx[i]为上文的k[i]
int cnt;//add函数用
struct hh{int dep,mep;}d[N];
void f1(int,int,int);
void f2(int,int,int);
bool f3(int,int,int);
void add(int,int);
int fd(int x,int sd,int f)//f为防止往父亲节点重复走
{
d[x].dep=sd;
int b=0;bool ok=0;
for(int i=ft[x];i;i=nx[i]) if(to[i]!=f) ok=1,b=max(b,fd(to[i],sd+1,x));//最大深度
if(!ok) b=sd;//如果没路走(叶节点),可以走到的最大深度为自生
d[x].mep=b;
return b;
}
int cmp(int s1,int s2){return s1>s2;}//从大到小
inline int read()
{
char c=getchar();int sum=0,f=1;
while(!(c>='0'&&c<='9')) {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') {sum=((sum<<1)+(sum<<3))+(c-'0');c=getchar();}
return sum*f;
}
int main()
{
n=read();k=read();
for(int i=1;i<n;i++)
{
int x=read(),y=read();
add(x,y);add(y,x);
}
f1(1,1,0);//第一次搜
maxn=0;//由于maxn是公用的,所以要清零
f2(yd,1,0);//第二次
maxn=0;
f3(yd,1,0);//找直径的完整路径
fd(zj[(zjs+1)/2],1,0);//从中点开始求可以到达的最深叶子节点的深度和其自身的深度
for(int i=1;i<=n;i++) gx[i]=d[i].mep-d[i].dep;//求gx
sort(gx+1,gx+n+1,cmp);//排序
int ans=0;
for(int i=k+1;i<=n;i++) ans=max(ans,gx[i]+1);//非核心城市里找最大值
printf("%d\n",ans);
return 0;
}
void f1(int x,int st,int f)
{
bool ok=0;
for(int i=ft[x];i;i=nx[i]) if(to[i]!=f) ok=1,f1(to[i],st+1,x);
if(!ok) //如果没路走,判断是不是最大值
{
if(st>maxn) yd=x,maxn=st;
return;
}
return;
}
void f2(int x,int st,int f)
{
bool ok=0;
for(int i=ft[x];i;i=nx[i])
{
if(to[i]!=f) ok=1;
}
if(!ok) //如果没路走,判断是不是最大值
{
if(st>maxn) ryd=x,maxn=st;
return;
}
for(int i=ft[x];i;i=nx[i]) if(to[i]!=f) f2(to[i],st+1,x);
return;
}
bool f3(int x,int st,int f)//用bool的原因看下面
{
if(x==ryd)
{
zj[st]=x;
zjs=st;
return 1;//走到另一端返回1
}
for(int i=ft[x];i;i=nx[i])
if(to[i]!=f)
if(f3(to[i],st+1,x))//如果返回1说明这样走可以走到另一端,可以记录路径,这样就不容易记错
{
zj[st]=x;//记录
return 1;//返回1
}
return 0;//怎么都找不到返回0
}
void add(int x,int y)
{
nx[++cnt]=ft[x];
ft[x]=cnt;
to[cnt]=y;
return ;
}