牛客小白月赛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';
}
}

#牛客创作赏金赛#