http://poj.org/problem?id=3107

这实际上就是找重心,在之前有做过:http://www.cnblogs.com/qlky/p/5780933.html

#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <cctype>
#include <vector>
#include <iterator>
#include <set>
#include <map>
#include <sstream>
using namespace std; #define mem(a,b) memset(a,b,sizeof(a))
#define pf printf
#define sf scanf
#define spf sprintf
#define pb push_back
#define debug printf("!\n")
#define MAXN 110000+5
#define MAX(a,b) a>b?a:b
#define blank pf("\n")
#define LL long long
#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())
#define pqueue priority_queue
#define INF 0x3f3f3f3f int n,m; struct node{int y,val,next;}tree[MAXN<<]; int head[MAXN],vis[MAXN],ptr=,dp[MAXN],num[MAXN],ans,tot,a[MAXN]; void init()
{
mem(head,-);
mem(vis,);
mem(dp,);
ans =INF;
tot = ;
ptr=;
}
void add(int x,int y)
{
tree[ptr].y = y;
tree[ptr].next = head[x];
head[x] = ptr++;
} void dfs(int rt)
{
num[rt]=vis[rt]=;
int tmp = ;
//pf("rt%d\n",rt);
for(int i = head[rt];i!=-;i=tree[i].next)
{
int y = tree[i].y;
if(vis[y]) continue;
dfs(y);
num[rt]+=num[y];
tmp = max(tmp,num[y]);
//pf("y%d %d\n",y,tmp);
}
tmp = max(tmp,n-num[rt]);
//pf("t%d %d %d\n",rt,tmp,ans);
if(tmp<ans)
{
ans = tmp;
tot = ;
a[tot++] = rt;
}
else if(tmp == ans) a[tot++] = rt;
} int main()
{
int i,j,k,t;
while(~sf("%d",&n))
{
init();
for(i=;i<n;i++)
{
int x,y;
sf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
dfs();
sort(a,a+tot);
pf("%d",a[]);
for(i=;i<tot;i++) pf(" %d",a[i]);
blank;
}
}

最新文章

  1. Lind.DDD.RedisClient~对StackExchange.Redis调用者的封装及多路复用技术
  2. Spring + SpringMVC + Druid + JPA(Hibernate impl) 给你一个稳妥的后端解决方案
  3. 引用外部css文件
  4. 改写libsvmread读取多标记数据集
  5. [moka同学笔记]一、Yii2.0课程笔记(魏曦老师教程)
  6. WKWebView API精讲(OC)
  7. 自动档车的P档和N档的区别
  8. Java BIO、NIO、AIO-------转载
  9. oracle表导入导出
  10. Linux系统中如何添加自己的库文件路径
  11. mac os 安装PIP 及异常“”Can&#39;t install python module: PyCharm Error: “byte-compiling is disabled, skipping”“”的解决方案
  12. (jzoj snow的追寻)线段树维护树的直径
  13. BeautifulSoup4库
  14. 1.5 A better alternative thing: React Native
  15. css加载动画...
  16. JSON Web Token(JWT)原理和用法介绍
  17. 1、话说linux内核
  18. Linux内核分析 读书笔记 (第五章)
  19. MySQL索引的使用方式和缺点
  20. Keepalived详解之 - LVS(IPVS)管理工具ipvsadm使用指南

热门文章

  1. 基于vue框架项目开发过程中遇到的问题总结(一)
  2. localStorage、sessionStorage、cookie的有效期和作用域问题
  3. 新姿势!Redis中调用Lua脚本以实现原子性操作
  4. P2498 [SDOI2012]拯救小云公主
  5. luogu2155 [SDOI2008]沙拉公主的困惑
  6. CF709B Checkpoints 模拟
  7. linux下mysql的安装部署
  8. 2.mybatis 的列名与数据库字段不对应
  9. 20. js继承的6种方式
  10. C# 事务提交(非数据库)