poj1655 树的重心 dfs
考虑具有N（1 <= N <= 20,000）个节点的树T，其编号为1 ... N.从树中删除任何节点会生成一个林：一个或多个树的集合。将节点的余额定义为通过从T中删除该节点而创建的林T中最大树的大小。
例如，考虑树：
删除节点4会生成两个树，其成员节点为{5}和{1,2,3,6,7}。这两棵树中较大的一个有五个节点，因此节点4的余额为五。删除节点1会生成三个大小相同的树林：{2,6}，{3,7}和{4,5}。这些树中的每一个都有两个节点，因此节点1的余额为2。
对于每个输入树，计算具有最小余额的节点。如果多个节点具有相等的余额，则输出编号最小的节点。
例如，考虑树：
删除节点4会生成两个树，其成员节点为{5}和{1,2,3,6,7}。这两棵树中较大的一个有五个节点，因此节点4的余额为五。删除节点1会生成三个大小相同的树林：{2,6}，{3,7}和{4,5}。这些树中的每一个都有两个节点，因此节点1的余额为2。
对于每个输入树，计算具有最小余额的节点。如果多个节点具有相等的余额，则输出编号最小的节点。
输入
第一行输入包含单个整数t（1 <= t <= 20），即测试用例的数量。每个测试用例的第一行包含一个整数N（1 <= N <= 20,000），即同余数。下一个N-1行每个包含两个空格分隔的节点号，它们是树中边的端点。没有边缘将被列出两次，并且将列出所有边缘。
产量
对于每个测试用例，打印包含两个整数的行，具有最小余额的节点的编号以及该节点的余额。
1、Unity3D 快捷键
2、Python下的机器学习工具scikit-learn
3、2016.2.17文件夹选择框及文件选择框
4、HTML-CSS-JS-JQ常用知识点总结
5、关于Java的=赋值操作和方法传递对象时的引用
样本输入
1 7 2 6 1 2 1 4 4 5 3 7 3 1
样本输出
1 2
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=2e5+10;
vector<int> v[maxn];
int siz[maxn];
int ma=inf,ans=inf;
int n;
void dfs(int x,int fa){
siz[x]=1;
int maxx=0;
for(int i=0;i<(int)v[x].size();i++){
int y=v[x][i];
if(y==fa) continue;
dfs(y,x);
siz[x]+=siz[y];
maxx=max(siz[y],maxx);
}
maxx=max(maxx,n-siz[x]);
if( maxx < ma ||( (maxx==ma) && x<ans )){
//具有最小余额的节点
//如果多个节点具有相等的余额 则输出编号最小的节点。
ma=maxx;
ans=x;
}
}
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
ma=inf,ans=inf;
for(int i=0;i<=n;i++)
v[i].clear(),siz[i]=0;
for(int i=1;i<n;i++){
int x,y;
scanf("%d%d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1,1); //1,1为起点开始搜
printf("%d %d\n",ans,ma);
}
return 0;
}
优质内容筛选与推荐>>
1、Unity3D 快捷键
2、Python下的机器学习工具scikit-learn
3、2016.2.17文件夹选择框及文件选择框
4、HTML-CSS-JS-JQ常用知识点总结
5、关于Java的=赋值操作和方法传递对象时的引用