题解
1.这k个城市一定是连成一团在中间的
2.把树展开,变成散发图,剩下的n-k个城市一定在最边缘的位置
3.拓扑排序
code
#include<bits/stdc++.h>
using namespace std;
vector<int> G[100005];
int du[100005]={0};
int depth[100005]={0};
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n,k;
cin>>n>>k;
for(int i=1;i<n;i++)
{
int x,y;
cin>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
queue<int> q;
for(int i=1;i<=n;i++)
{
du[i]=G[i].size();
if(du[i]==1) q.push(i);
}
int left=n-k,ans=0;
while(left--)
{
int now=q.front();
q.pop();
ans=max(ans,depth[now]);
for(auto next:G[now])
{
if(--du[next]==1)
{
depth[next]=depth[now]+1;
q.push(next);
}
}
}
cout<<ans+1;
return 0;
}
标签:P5536,int,核心,back,100005,XR,tie
From: https://www.cnblogs.com/pure4knowledge/p/18111333