poj 1655 Balancing Act(树的重心)
发布时间：2020-12-13 20:44:48 所属栏目：PHP教程 来源：网络整理
导读：Balancing Act Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 9913 Accepted: 4069 Description Consider a tree T with N (1 = N = 20,000) nodes numbered 1...N. Deleting any node from the tree yields a forest: a collection of one o
|
Balancing Act
Description
Consider a tree T with N (1 <= N <= 20,000) nodes numbered 1...N. Deleting any node from the tree yields a forest: a collection of one or more trees. Define the balance of a node to be the size of the largest tree in the forest T created by deleting that node
from T.
For example,consider the tree:
Deleting node 4 yields two trees whose member nodes are {5} and {1,2,3,6,7}. The larger of these two trees has five nodes,thus the balance of node 4 is five. Deleting node 1 yields a forest of three trees of equal size: {2,6},{3,7},and {4,5}. Each of these trees has two nodes,so the balance of node 1 is two. For each input tree,calculate the node that has the minimum balance. If multiple nodes have equal balance,output the one with the lowest number. Input
The first line of input contains a single integer t (1 <= t <= 20),the number of test cases. The first line of each test case contains an integer N (1 <= N <= 20,000),the number of congruence. The next N⑴ lines each contains two space-separated node numbers
that are the endpoints of an edge in the tree. No edge will be listed twice,and all edges will be listed.
Output
For each test case,print a line containing two integers,the number of the node with minimum balance and the balance of that node.
Sample Input 1
7
2 6
1 2
1 4
4 5
3 7
3 1
Sample Output 1 2
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define ll long long
#define N 21000
#define mem(a,t) memset(a,t,sizeof(a))
const int inf=1000005;
int cnt,n;
struct node
{
int v,next;
}e[N*2];
int head[N];
int num[N];
int ans,index;
void add(int u,int v)
{
e[cnt].v=v;
e[cnt].next=head[u];
head[u]=cnt++;
}
void dfs(int u,int len,int fa)
{
int i,v,tmp=0;
num[u]=1;
for(i=head[u];i!=⑴;i=e[i].next)
{
v=e[i].v;
if(v!=fa)
{
dfs(v,len+1,u);
tmp=max(tmp,num[v]);
num[u]+=num[v];
}
}
int t=max(tmp,n-num[u]);
if(t<=ans)
{
if(u<index||t<ans)
{
ans=t;
index=u;
}
}
}
int main()
{
//freopen("in.txt","r",stdin);
int i,u,t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
cnt=0;
mem(head,⑴);
for(i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
mem(num,0);
ans=n;
dfs(1,⑴);
printf("%d %d
",index,ans);
}
return 0;
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
