首页 > 代码库 > POJ 2378 Tree Cutting 子树统计
POJ 2378 Tree Cutting 子树统计
题目大意:给出一棵树。将树中的一个节点去掉之后,这棵树会分裂成一些联通块。求去掉哪些点之后。全部联通块的大小不超过全部节点的一半。并按顺序输出。
思路:基础的子树统计问题,仅仅要深搜一遍就能够出解。这个步骤和求树的重心非常像,是树分治的基础。
CODE:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 10010 using namespace std; int points; int head[MAX],total; int next[MAX << 1],aim[MAX << 1]; int size[MAX]; bool ans[MAX]; inline void Add(int x,int y); void DFS(int x,int last); int main() { cin >> points; for(int x,y,i = 1;i < points; ++i) { scanf("%d%d",&x,&y); Add(x,y),Add(y,x); } DFS(1,0); for(int i = 1;i <= points; ++i) if(ans[i]) printf("%d\n",i); return 0; } inline void Add(int x,int y) { next[++total] = head[x]; aim[total] = y; head[x] = total; } void DFS(int x,int last) { size[x] = 1; int max_size = 0; for(int i = head[x];i;i = next[i]) { if(aim[i] == last) continue; DFS(aim[i],x); size[x] += size[aim[i]]; max_size = max(max_size,size[aim[i]]); } max_size = max(max_size,points - size[x]); if(max_size <= (points >> 1)) ans[x] = true; }
POJ 2378 Tree Cutting 子树统计
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。