P1395 会议

题目描述

有一个村庄居住着n个村民,有n-1条路径使得这n个村民的家联通,每条路径的长度都为1。现在村长希望在某个村民家中召开一场会议,村长希望所有村民到会议地点的距离之和最小,那么村长应该要把会议地点设置在哪个村民的家中,并且这个距离总和最小是多少?若有多个节点都满足条件,则选择节点编号最小的那个点。

输入输出格式

输入格式:

第一行。一个数n,表示有n个村民。

接下来n-1行,每行两个数字a和b,表示村民a的家和村民b的家之间存在一条路径。

输出格式:

一行输出两个数字x和y

x表示村长将会在哪个村民家中举办会议

y表示距离之和的最小值

输入输出样例

输入样例#1:

4
1 2
2 3
3 4
输出样例#1:

2 4

说明

【数据范围】

70%数据n<=1000

100%数据n<=50000

代码

 #include<cstdio>
#include<algorithm> using namespace std;
const int MAXN=,INF=1e9;
struct Edge{
int to,nxt;
}e[MAXN<<];
int n,cnt,ans,minn,size=INF;
int head[MAXN<<],son[MAXN],dep[MAXN];
bool vis[MAXN]; void add(int u,int v)
{
++cnt;
e[cnt].to = v;
e[cnt].nxt = head[u];
head[u] = cnt;
} void dfs(int cur)
{
vis[cur] = true;
son[cur] = ;
int tmp = ;
for (int i=head[cur]; i; i=e[i].nxt)
{
if (!vis[e[i].to])
{
dfs(e[i].to);
son[cur] += son[e[i].to]+; //加上自己
tmp = max(tmp,son[e[i].to]+) ;
}
}
tmp = max(tmp,n-son[cur]-);
if(size>tmp || (tmp==size&&ans>cur))
{
ans = cur;
size = tmp;
}
}
void dfsdep(int x,int p,int d)
{
dep[x] = d;
for (int i=head[x]; i; i=e[i].nxt)
if(p!=e[i].to)
dfsdep(e[i].to,x,d+);
}
int main()
{
scanf("%d",&n);
for (int x,y,i=; i<n; ++i)
{
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
dfs();
dfsdep(ans,ans,);
for (int i=; i<=n; ++i)
minn += abs(dep[ans]-dep[i]);
printf("%d %d",ans,minn);
return ;
}

最新文章

  1. web 前端常用组件【07】弹出层 Layer
  2. set、def、lambda、内置函数、文件操作
  3. 三星framebuffer驱动代码分析
  4. 编写一个Shape类,具有属性:周长和面积; 定义其子类三角形和矩形,分别具有求周长的方法。 定义主类E,在其main方法中创建三角形和矩形类的对象, 并赋给Shape类的对象a、b,使用对象a、b来测试其特性。
  5. 利用ServletFileUpload组件上传文件
  6. 纯javascript联动的例子
  7. POJ 2226 Muddy Fields(最小顶点覆盖)
  8. location对象的属性和方法应用(解析URL)
  9. 写markdown博客如何截图并快速上传到图床——记一个工具插件的实现
  10. python爬微信公众号前10篇历史文章(3)-lxml&amp;xpath初探
  11. linux进程内存布局
  12. python学习中的bug
  13. TCP/IP协议---UDP协议
  14. 解决Win8系统修改IP地址后保存不了的方法
  15. elasticsearch设置外部可访问
  16. 如何优雅的使用mybatis
  17. 自定义cnblogs样式小结
  18. 20145314郑凯杰《网络对抗技术》实验8 WEB基础实践
  19. 【干货】国外程序员整理的 C++ 资源大全(转)
  20. Android Studio failed to create error code -6解决方法

热门文章

  1. ubuntu16.4安装 VirtualBox
  2. git(github)常用命令
  3. pt-table-sync
  4. Java中阻塞队列的使用
  5. java导入、导出
  6. cudaMallocPitch()
  7. wordpress问题集锦
  8. Spring 学习之依赖注入
  9. 3.2.5 Magic Squares 魔板
  10. matlab2018a安装后帮助文档打不开解决方法