木の重心を求めます(POJ 1655)
1540 ワード
标题:n(n<=2000)個のノードを持つ木を与え、そのうちの1つのノードを削除すると、1本の木、または複数の木が形成され、いずれかのノードを削除するバランスが最大となる木のノード数を定義し、どのノードを削除した後、バランスを最小にすることができ、つまり木の重心を求める.
num配列レコードの現在のノードをルートとするサブツリー要素の個数を定義し、ans配列レコードがノードを削除した後のバランスを記録します.
num配列レコードの現在のノードをルートとするサブツリー要素の個数を定義し、ans配列レコードがノードを削除した後のバランスを記録します.
#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#include"algorithm"
#include"iostream"
#define M 20009
using namespace std;
struct node
{
int u,v,next;
}edge[M*2];
int t,num[M],head[M],ans[M],n;
void init()
{
t=0;
memset(head,-1,sizeof(head));
}
void add(int u,int v)
{
edge[t].u=u;
edge[t].v=v;
edge[t].next=head[u];
head[u]=t++;
}
void dfs(int u,int f)
{
num[u]=1;
ans[u]=0;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].v;
if(v==f)continue;
dfs(v,u);
num[u]+=num[v];
ans[u]=max(ans[u],num[v]);
ans[v]=max(ans[v],n-num[v]);
}
}
int main()
{
int T,i;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
init();
for(i=1;i<n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
dfs(1,-1);
int id=1;
for(i=1;i<=n;i++)
if(ans[id]>ans[i])
id=i;
printf("%d %d
",id,ans[id]);
}
}