题目链接:http://poj.org/problem?id=2378

一棵树,去掉一个点剩下的每棵子树节点数不超过n/2。问有哪些这样的点,并按照顺序输出。

dfs回溯即可。

 //#pragma comment(linker, "/STACK:102400000, 102400000")
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;
typedef long long LL;
typedef pair <int, int> P;
const int N = 1e4 + ;
vector <int> ans;
struct Edge {
int next, to;
}edge[N << ];
int d[N], head[N], cnt, n; inline void add(int u, int v) {
edge[cnt].next = head[u];
edge[cnt].to = v;
head[u] = cnt++;
} void dfs(int u, int p) {
bool ok = true;
d[u] = ;
for(int i = head[u]; ~i; i = edge[i].next) {
int v = edge[i].to;
if(v == p)
continue;
dfs(v, u);
if(d[v] * > n)
ok = false;
d[u] += d[v];
}
if((n - d[u]) * > n)
ok = false;
if(ok)
ans.push_back(u);
} int main()
{
while(~scanf("%d", &n)) {
int u, v;
memset(head, -, sizeof(head));
cnt = ;
ans.clear();
for(int i = ; i < n; ++i) {
scanf("%d %d", &u, &v);
add(u, v);
add(v, u);
}
dfs(, -);
sort(ans.begin(), ans.end());
for(int i = ; i < ans.size(); ++i) {
printf("%d\n", ans[i]);
}
}
return ;
}

最新文章

  1. geotrellis使用(二十一)自动导入数据
  2. 固定在网页顶部跟随滚动条滑动而滑动的DIV层
  3. C#:枚举
  4. DOS命令行中的双引号
  5. Response.Write页面跳转
  6. web 项目 布在tomcat服务器上出现的问题小记
  7. 3. Android框架和工具之 xUtils(DbUtils )
  8. oracle游标小试
  9. 【图论】【宽搜】【染色】NCPC 2014 A Ades
  10. iphone开发之适配iphone5
  11. PHP基础温习之echo print printf sprintf print_r var_dump的用法与区别
  12. 快速的CDN加速服务
  13. Splay伸展树入门(单点操作,区间维护)附例题模板
  14. objective-c 2.0的字面量Literals
  15. Java 200+ 面试题补充 ThreadLocal 模块
  16. 2018.11.25 AMC-ICPC 亚洲区域赛(焦作站)吊银
  17. [katalon] 页面切换
  18. P499 usebrass2
  19. POJ2594 Treasure Exploration(最小路径覆盖)
  20. 设置定时任务(Timer类的介绍)

热门文章

  1. get 与post 的接收传值方式
  2. php实现一致性哈希算法
  3. 通过外部接口 根据ip获取城市名
  4. [Papers]NSE, $u$, Lorentz space [Bosia-Pata-Robinson, JMFM, 2014]
  5. ADO.NET+Access: 1,标准表达式中数据类型不匹配
  6. 6. ActionBar详解
  7. 如何查看python selenium的api
  8. 排列组合+组合数取模 HDU 5894
  9. linux c下mysql编程样例
  10. ajax 模仿百度下拉