题解:【XR-3】核心城市
思路一:考虑由特例推广到一般
1、很容易想到先考虑一个关键点的情况,然后再推广到一般情况。
2、一个点肯定选距离上最平衡的那个点,即树的中心。接着在中心周围贪心的选剩下的(k-1)个关键点即可。
3、这里有一个误区:
各点到某点的距离最小,是找树的中心而不是重心!!!
各点到某点的距离最小,是找树的中心而不是重心!!!
各点到某点的距离最小,是找树的中心而不是重心!!!
(树的重心:最小化 最大的子树大小;树的中心:最小化 各点到某点的距离,即树的直径的中点)
#include<bits/stdc++.h>
#define F(i,l,r) for(int i=l;i<=r;++i)
#define G(i,r,l) for(int i=r;i>=l;--i)
#define int long long
using namespace std;
char buf[100],*p1=buf,*p2=buf;
inline int gc(){return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100,stdin),p1==p2)?EOF:*p1++;}
inline int rd(){
int x=0; char ch; bool f=1;
while(!isdigit(ch=gc())) f^=(ch=='-');
do x=(x<<3)+(x<<1)+(ch^48); while(isdigit(ch=gc()));
return x;
}
const int N=1e5+5;
struct node{ int v,ne; }e[N<<1];
int first[N],dis[N],len[N],pre[N],a[N];
int n,idx=0,k,cx=0,mn=1000000000;
void add(int x,int y){ e[++idx]=(node){y,first[x]}; first[x]=idx;}
void go(int u,int f){
dis[u]=dis[f]+1; pre[u]=f;
if(dis[u]>dis[cx]) cx=u;
for(int i=first[u];i;i=e[i].ne) if(e[i].v!=f) go(e[i].v,u);
}
void dfs(int u,int f){
len[u]=1;
for(int i=first[u];i;i=e[i].ne){
int v=e[i].v; if(v==f) continue;
dfs(v,u);
len[u]=max(len[v]+1,len[u]);
}
}
signed main(){
n=rd(),k=rd(); int u,v;
F(i,1,n-1) u=rd(),v=rd(),add(u,v),add(v,u);
go(1,0);
dis[cx]=0;
go(cx,0);
int cnt=1,iii=(dis[cx]+1)/2;
while(cnt!=iii && pre[cx]) cx=pre[cx],++cnt;
dfs(cx,0);
sort(len+1,len+n+1);
printf("%lld",len[n-k]);
return 0;
}
思路二:考虑逆向思维
1、发现 “选k个关键点放入圈中” 等同于 “选(n-k)个非关键点出圈”。
2、而由题可知,k个关键点是一个连通块,所以叶子结点是最先出圈的。由此确定,删点是从外而内一层层删。
3、用topsort模拟删点的过程即可,由于是用广搜实现topsort,因此点是”一轮一轮删的“,删完(n-k)个点后到了第几轮,答案就是几。
标签:p1,int,题解,len,rd,cx,核心,XR,buf From: https://www.cnblogs.com/superl61/p/17922422.html