vector建图被卡了。。改为链式前向星500ms过的。。差了四倍多?。。。

表示不太会用链表建图啊。。自己试着写的,没看模板。。嗯。。果然错了。。落了一句话orz

树的重心就是找到一个树中一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后,生成的多棵树尽可能平衡。

根据定义很容易求得。

/***********************************************
Problem: 3107 User: G_lory
Memory: 4440K Time: 500MS
Language: C++ Result: Accepted
***********************************************/ #include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <complex>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cassert>
using namespace std;
typedef long long ll; const int N = 500005; struct Edge {
int to, next;
} edge[N];
int head[N]; int cnt;
int sz[N];
int maxn[N]; int n; void add_edge(int u, int v) // 双向边
{
edge[cnt].to = v;
edge[cnt].next = head[u];
head[u] = cnt;
cnt++; edge[cnt].to = u;
edge[cnt].next = head[v];
head[v] = cnt;
cnt++;
} int ans;
void dfs(int u, int pre)
{
sz[u] = 0;
int temp = 0;
for (int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].to;
if (v == pre) continue;
dfs(v, u);
sz[u] += sz[v] + 1;
temp = max(temp, sz[v] + 1);
}
temp = max(n - sz[u] - 1, temp);
maxn[u] = temp;
ans = min(temp, ans);
} int main()
{
while (~scanf("%d", &n))
{
int a, b;
memset(head, -1, sizeof head);
cnt = 1;
for (int i = 1; i < n; ++i)
{
scanf("%d%d", &a, &b);
add_edge(a, b);
}
ans = n;
dfs(1, -1);
int ok = 1;
for (int i = 1; i <= n; ++i)
{
if (maxn[i] == ans)
{
if (ok) ok = 0;
else printf(" ");
printf("%d", i);
}
}
printf("\n");
}
return 0;
}

  

最新文章

  1. WebAPI接口返回ArrayList包含Dictionary对象正确解析
  2. Android编码规范02
  3. MVC4下配置log4net 五部曲
  4. Null Object模式
  5. &ldquo;耐撕&rdquo;团队 2016.3.25 站立会议
  6. springboot+maven快速构建项目
  7. 一行代码解决各种IE兼容问题,IE6,IE7,IE8,IE9,IE10(转)
  8. 注解在android中的使用
  9. JVM常见垃圾回收算法
  10. Java 面试知识点解析(五)——网络协议篇
  11. KVM 热迁移
  12. JS(JavaScript)的进一步了解6(更新中&#183;&#183;&#183;)
  13. Docker环境下的Mysql8 实现主从数据库数据同步方案
  14. zabbix4.0离线快速编译安装(编译安装方法)
  15. ui-router 1.0 002 未登录跳转到login
  16. Java Web项目中连接Access数据库的配置方法
  17. iOS RSA非对称加密测试流程
  18. js模拟点击打开超链接
  19. iOS8 CIGlassDistortion滤镜的使用
  20. gRPC初探——概念介绍以及如何构建一个简单的gRPC服务

热门文章

  1. 《JavaScript启示录》摘抄
  2. java 对象 类 知识点 概览
  3. ANDROID_MARS学习笔记_S01原始版_017_绑定SERVICE
  4. RichEdit 各个版本介绍
  5. 135. Candy
  6. Android list1去除list2中的元素
  7. 在ubuntu系统荣品开发配套JDK安装
  8. file_operations结构2
  9. Cookie的前后台应用
  10. 深刻理解C#的传值调用和传引用调用