POJ 2378 Tree Cutting (DFS)
2024-10-11 23:42:53
题目链接: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 ;
}
最新文章
- geotrellis使用(二十一)自动导入数据
- 固定在网页顶部跟随滚动条滑动而滑动的DIV层
- C#:枚举
- DOS命令行中的双引号
- Response.Write页面跳转
- web 项目 布在tomcat服务器上出现的问题小记
- 3. Android框架和工具之 xUtils(DbUtils )
- oracle游标小试
- 【图论】【宽搜】【染色】NCPC 2014 A Ades
- iphone开发之适配iphone5
- PHP基础温习之echo print printf sprintf print_r var_dump的用法与区别
- 快速的CDN加速服务
- Splay伸展树入门(单点操作,区间维护)附例题模板
- objective-c 2.0的字面量Literals
- Java 200+ 面试题补充 ThreadLocal 模块
- 2018.11.25 AMC-ICPC 亚洲区域赛(焦作站)吊银
- [katalon] 页面切换
- P499 usebrass2
- POJ2594 Treasure Exploration(最小路径覆盖)
- 设置定时任务(Timer类的介绍)
热门文章
- get 与post 的接收传值方式
- php实现一致性哈希算法
- 通过外部接口 根据ip获取城市名
- [Papers]NSE, $u$, Lorentz space [Bosia-Pata-Robinson, JMFM, 2014]
- ADO.NET+Access: 1,标准表达式中数据类型不匹配
- 6. ActionBar详解
- 如何查看python selenium的api
- 排列组合+组合数取模 HDU 5894
- linux c下mysql编程样例
- ajax 模仿百度下拉