Pagini recente » Cod sursa (job #2443679) | Cod sursa (job #3040130) | Cod sursa (job #786039) | Cod sursa (job #149870) | Cod sursa (job #1710085)
#include <stdio.h>
#include <algorithm>
#include<vector>
#include<queue>
#define pb push_back
#define maxn 100005
#define inf 0x3f3f3f3f
using namespace std;
int T,n,nrc,L,R;
int v[maxn],grade[maxn],d[maxn];
vector<int> l[maxn];
int q[maxn],sel[maxn],center[2];
vector<int> dist;
void read()
{
int x,y;
scanf("%d",&n);
for(int i=1;i<n;i++)
{
scanf("%d %d",&x,&y);
l[x].pb(y); grade[y]++;
l[y].pb(x); grade[x]++;
}
}
void get_center()
{
int k;
L=1; R=0;
for(int i=1;i<=n;i++)
if( grade[i]==1 )
q[++R]=i;
int nrn=n;
for(;nrn>2;)
{
int cnt=R-L+1; nrn-=cnt;
for(int i=1;i<=cnt;i++,L++)
{
k=q[L];
for(unsigned j=0;j<l[k].size();j++)
if(!sel[l[k][j]])
{
grade[l[k][j]]--;
if( grade[l[k][j]]==1 )
q[++R]=l[k][j], sel[l[k][j]]=1;
}
}
}
nrc=R-L+1;
for(int i=0;i<nrc;i++)
center[i]=q[L+i];
printf("%d\n",nrc);
printf("%d %d\n",center[0],center[1]);
}
void dfs(int k)
{
v[k]=1; d[k]=0;
for(unsigned int i=0;i<l[k].size();i++)
if( !v[l[k][i]])
{
dfs(l[k][i]);
d[k]=max(d[k],1+d[l[k][i]]);
}
if( l[k].size()==1 ) dist.pb(d[k]);
}
int solve()
{
int Min= inf;
dfs(center[0]);
sort(dist.begin(),dist.end());
if( dist.size()==1 )
return dist[dist.size()-1];
int X = dist[dist.size()-1]-dist[0];
dist[dist.size()-1]-=X;
sort(dist.begin(),dist.end());
Min=min(Min, dist[dist.size()-1]+dist[dist.size()-2] );
if( nrc<2 ) return Min;
for(int i=1;i<=n;i++) v[i]=d[i]=0;
dist.clear();
dfs(center[1]);
sort(dist.begin(),dist.end());
if( dist.size()==1 )
return dist[dist.size()-1];
X = dist[dist.size()-1]-dist[0];
dist[dist.size()-1]-=X;
sort(dist.begin(),dist.end());
Min=min(Min, dist[dist.size()-1]+dist[dist.size()-2] );
return Min;
}
void clear_data()
{
L=R=0; nrc=0;
for(int i=1;i<=n;i++)
{
v[i]=d[i]=grade[i]=0;
sel[i]=0;
l[i].clear();
}
}
int main()
{
freopen("revolta.in","r",stdin);
freopen("revolta.out","w",stdout);
scanf("%d",&T);
for(;T;T--)
{
read();
get_center();
printf("%d\n",solve());
clear_data();
}
return 0;
}