题目链接: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();
}

最新文章

  1. android自定义控件(4)-自定义水波纹效果
  2. Azkaban 2.5.0 job type 插件安装
  3. iframe父子页面之间相互调用元素和函数
  4. 使用Android Studio搭建Android集成开发环境
  5. 尽量少用Include
  6. Linux 网络设备驱动程序设计(2)
  7. POJ 2533
  8. [转载]Android开发常用调试技术记录
  9. PHP内核探索之变量 图解
  10. python实时处理log文件脚本
  11. ie6常见的兼容性
  12. JQ中的clone()方法与DOM中的cloneNode()方法
  13. 在Activity之间使用Intent传值和Bundle传值的区别和方式
  14. iphone手机中对于html和css的一些特殊处理
  15. 洛谷 P2764 解题报告
  16. async 和 await 之异步编程的学习
  17. spring注解第05课 FactoryBean
  18. Chrome表单文本框自动填充黄色背景色样式
  19. 处理返回键劫持(结合vue)
  20. vue-router基本概念及使用

热门文章

  1. lua学习笔记(二)
  2. 【问题记录】web项目访问时出现404
  3. win10 下eclipse tomcat 热部署问题?
  4. mysqldump命令使用详解
  5. java中业务接口
  6. Nginx结合GeoIP库
  7. UIApplicationDelegate 各方法回调时机
  8. iOS main函数讲解
  9. Android异步载入全解析之使用AsyncTask
  10. Opennms -安装