dfs求樹的重心。
然後記得用前向星,用vector會t。
然後就是又是慣例的poj過量測試,數組開大一點。
代碼:
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define ps push_back
using namespace std;
const int maxn=5e5+5;
//vector<int>edg[maxn];
struct node
{
int to;
int nex;
}edg[maxn+10000];
int head[maxn];
int siz[maxn];
int ms[maxn];
vector<int>ans;
int cnt;
void add(int u, int v)
{
edg[cnt].to=v;
edg[cnt].nex=head[u];
head[u]=cnt++;
}
void dfs(int x, int fa)
{
siz[x]=ms[x]=0;
// for(int i=0; i<(int)edg[x].size(); i++)
for(int i=head[x]; i!=-1; i=edg[i].nex)
{
if(edg[i].to!=fa)
{
dfs(edg[i].to, x);
siz[x]+=siz[edg[i].to];
ms[x]=max(ms[x], siz[edg[i].to]);
}
}
siz[x]++;
// cout<<x<<" "<<siz[x]<<endl;
return;
}
int main()
{
int x, y, n, i, j;
cin>>n;
for(i=1; i<=n; i++)head[i]=-1;
for(i=0; i<n-1; i++)
{
scanf("%d%d", &x, &y);
add(x, y);
add(y, x);
}
dfs(1, 0);
int mi=maxn+10;
for(i=1; i<=n; i++)
{
ms[i]=max(ms[i], n-siz[i]);
if(ms[i]<mi)
{
mi=ms[i];
}
}
for(i=1; i<=n; i++)
{
if(ms[i]==mi)
{
ans.ps(i);
}
}
sort(ans.begin(), ans.end());
printf("%d", ans[0]);
for(i=1; i<(int)ans.size(); i++)
{
printf(" %d", ans[i]);
}
printf("\n");
return 0;
}