题意:求树的重心,若有多个,全部打印出来。

思路:

  树的重心:在删除点v后,森林中的每棵树的节点数尽量均匀,若最大的那棵树的节点数最小,称v为树的重心。

  这道题只是求树的所有重心,当且经当这棵树有对称性质时才有多重心,因此一棵树的重心最多不会超过2个。也是一遍DFS就可以搞定了,参考这个。

 //#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <deque>
#include <algorithm>
#include <vector>
#include <iostream>
#define pii pair<int,int>
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define INF 0x7f7f7f7f
#define LL long long
using namespace std;
const double PI = acos(-1.0);
const int N=;
int n, cnt, edge_cnt, head[N]; struct node
{
int from, to, next;
node(){};
node(int from,int to,int next):from(from),to(to),next(next){};
}edge[N*]; void add_node(int from,int to)
{
edge[edge_cnt]=node(from,to,head[from]);
head[from]=edge_cnt++;
}
deque<int> que; int DFS(int t,int far)
{
node e;
int big=, sum=;
for(int i=head[t]; i!=-; i=e.next)
{
e=edge[i];
if(e.to==far) continue; int tmp=DFS(e.to, t);
big=max(big, tmp);
sum+=tmp;
}
big=max(big, n-sum-); if(big<=cnt)
{
if(big<cnt) que.clear();
cnt=big;
que.push_back(t);
}
return sum+;
} int main()
{
//freopen("input.txt", "r", stdin);
int a, b;
while(~scanf("%d",&n))
{
edge_cnt=;
cnt=INF;
memset(head,-,sizeof(head)); for(int i=; i<n; i++)
{
scanf("%d%d",&a,&b);
add_node(a,b);
add_node(b,a);
}
DFS(,-);
sort(que.begin(),que.end());
while(!que.empty())
{
printf("%d ",que.front());
que.pop_front();
}
puts("");
}
return ;
}

AC代码

最新文章

  1. java使double保留两位小数的多方法 java保留两位小数
  2. js 函数总结
  3. struts标签
  4. Android 防止OOM优化
  5. 收集C#常用类:自己写的一个DBHelper类
  6. 如何给input[file]定义cursor
  7. int android.graphics.Bitmap.getRowBytes()
  8. 安装 macbook 双系统( OS X 和 Ubuntu )
  9. canvas toDataUrl 跨域问题
  10. Android四大组件--Broadcast Receiver具体解释
  11. C++ 中的计时器
  12. 201521123029《Java程序设计》第1周学习总结
  13. 我不是bug神(JVM问题排查)
  14. java网页爬数据获取class中的空格
  15. 【vue】移动端demo资料
  16. 使用mybatis assembly插件打成tar包,在linux系统中运行服务
  17. 【速读】——Shangxuan Tian——【ICCV2017】WeText_Scene Text Detection under Weak Supervision
  18. left join on +多条件与where区别
  19. 前端开发模拟数据------webpack-api-mocker
  20. 多元高斯分布(The Multivariate normal distribution)

热门文章

  1. Algorithm-4th part I 学习进度 (7/12)
  2. Tomcat之the jre_home environment variable is not defined correctly this environment variable is need
  3. python 三元表达式 列表推导式,生成器表达式。递归,匿名函数, 内置函数
  4. Attributes.Add用途与用法
  5. spring中的依赖注入
  6. [Xcode 实际操作]一、博主领进门-(14)在顶部状态栏显示风火轮以及为应用程序添加应用图标
  7. ISO 8 自适应cell
  8. nutzboot dubbo zookeeper简单使用
  9. [題解]luogu_P1854 花店櫥窗佈置
  10. Tinghua Data Mining