牛客小白月赛119 D

BFS,一开始把所有叶子存入队列,每次向内延伸。对于每个节点记录下延伸的轮数(它等于最近叶子节点的距离)

最终找出记录值最远的一些点即可。

#include<bits/stdc++.h>
using namespace std;

const int N=2e5+5;
vector<int> e[N];
int d[N],deg[N],vst[N];

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int T; cin>>T;
while(T--)
{
int n; cin>>n;
for(int i=1;i<=n;i++)
{
e[i].clear();
d[i]=0; deg[i]=0; vst[i]=0;
}
for(int i=1,u,w;i<n;i++)
{
cin>>u>>w;
e[u].push_back(w);
e[w].push_back(u);
deg[u]++; deg[w]++;
}

queue<int> q;
for(int i=1;i<=n;i++)
if(deg[i]==1)
q.push(i), vst[i]=1;

while(!q.empty())
{
int x=q.front(); q.pop();
for(auto y:e[x])
{
if(vst[y]) continue;
d[y]=d[x]+1;
vst[y]=1;
q.push(y);
}
}

int mx=0;
for(int i=1;i<=n;i++)
if(deg[i]>1)
mx=max(mx,d[i]);

vector<int> ans;
for(int i=1;i<=n;i++)
if(deg[i]>1 && d[i]==mx)
ans.push_back(i);

cout<<ans.size()<<'\n';
for(auto x:ans) cout<<x<<' ';
cout<<'\n';
}
}

#牛客创作赏金赛#
全部评论
接好运
点赞 回复 分享
发布于 07-29 17:09 新加坡
忍耐王
点赞 回复 分享
发布于 07-29 17:09 新加坡

相关推荐

用微笑面对困难:不是你千万别小看这家公司,他们的预估市值成倍上涨,三次在报告看见这个公司了,总之如果是给股权的话可以试试,未来没准真能发家致富哈哈哈哈
点赞 评论 收藏
分享
评论
5
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务