BZOJ 3391 [Usaco2004 Dec]Tree Cutting网络破坏:dfs【无根树 节点分枝子树大小】
2024-08-29 08:56:48
题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3391
题意:
给你一棵无根树,求分支size均不大于一半点数的点。
题解:
假定1为根。
dfs时统计siz[i]和par[i]。
对于每个节点判断一下子树大小siz[son]和自己往上的子树大小n - siz[now]。
AC Code:
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#define MAX_N 10005 using namespace std; int n;
int par[MAX_N];
int siz[MAX_N];
vector<int> ans;
vector<int> edge[MAX_N]; void read()
{
cin>>n;
int a,b;
for(int i=;i<n-;i++)
{
cin>>a>>b;
edge[a].push_back(b);
edge[b].push_back(a);
}
} void dfs(int now,int p)
{
par[now]=p;
siz[now]=;
for(int i=;i<edge[now].size();i++)
{
int temp=edge[now][i];
if(temp!=p)
{
dfs(temp,now);
siz[now]+=siz[temp];
}
}
} void solve()
{
dfs(,-);
for(int i=;i<=n;i++)
{
int flag=true;
for(int j=;j<edge[i].size();j++)
{
int temp=edge[i][j];
if(temp!=par[i] && siz[temp]*>n)
{
flag=false;
break;
}
}
if((n-siz[i])*>n) flag=false;
if(flag) ans.push_back(i);
}
} void print()
{
if(!ans.size()) cout<<"NONE"<<endl;
else
{
for(int i=;i<ans.size();i++)
{
cout<<ans[i]<<endl;
}
}
} int main()
{
read();
solve();
print();
}
最新文章
- android自定义控件(4)-自定义水波纹效果
- Azkaban 2.5.0 job type 插件安装
- iframe父子页面之间相互调用元素和函数
- 使用Android Studio搭建Android集成开发环境
- 尽量少用Include
- Linux 网络设备驱动程序设计(2)
- POJ 2533
- [转载]Android开发常用调试技术记录
- PHP内核探索之变量 图解
- python实时处理log文件脚本
- ie6常见的兼容性
- JQ中的clone()方法与DOM中的cloneNode()方法
- 在Activity之间使用Intent传值和Bundle传值的区别和方式
- iphone手机中对于html和css的一些特殊处理
- 洛谷 P2764 解题报告
- async 和 await 之异步编程的学习
- spring注解第05课 FactoryBean
- Chrome表单文本框自动填充黄色背景色样式
- 处理返回键劫持(结合vue)
- vue-router基本概念及使用