POJ3107 树的重心

题解:只不过如果有求多个点,输出所有方案。

 #include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#define N 50007
#define inf 1000000009
using namespace std; int n,id,mnum;
int siz[N];
int cnt,head[N],next[N*],rea[N*];
vector<int>q; void add(int u,int v)
{
next[++cnt]=head[u];
head[u]=cnt;
rea[cnt]=v;
}
void dfs(int u,int fa)
{
int sum=,msiz=-;
siz[u]=;
for (int i=head[u];i!=-;i=next[i])
{
int v=rea[i];
if (v==fa) continue;
dfs(v,u);
siz[u]+=siz[v];
msiz=max(msiz,siz[v]);
}
msiz=max(msiz,n-siz[u]);
if (msiz==mnum) q.push_back(u);
else
if (msiz<mnum)
{
mnum=msiz;
q.clear();
q.push_back(u);
}
}
int main()
{
scanf("%d",&n);
memset(head,-,sizeof(head));
memset(siz,,sizeof(siz));
for (int i=,x,y;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y),add(y,x);
}
mnum=inf;
dfs(,-);
sort(q.begin(),q.end());
for (int i=;i<q.size();i++)
printf("%d ",q[i]);
}
上一篇:poj3107树的重心


下一篇:Solr入门之SolrServer实例化方式