//以一号节点为根节点,求出所有节点到根结点的距离,以及所有点的子节点的个数
//然后计算根据已知信息计算所有节点到当前结点的距离
//然后扫描n个点,O(n)求解
#include<bits/stdc++.h>
using namespace std;
const int maxn = ;
struct node {
int y, net;
}e[maxn << ];
int f[maxn], h[maxn];//h表示以当前节点的根结点的子节点的个数,f表示所有子节点到当前节点的距离和
int n;
int lin[maxn], len = ;
int id; inline int read() {
int x = , y = ;
char ch = getchar();
while(!isdigit(ch)) {
if(ch == '-') y = -;
ch = getchar();
}
while(isdigit(ch)) {
x = (x << ) + (x << ) + ch - '';
ch = getchar();
}
return x * y;
} inline void insert(int xx, int yy) {
e[++len].y = yy;
e[len].net = lin[xx];
lin[xx] = len;
} int son_num(int x, int fa) {
for(int i = lin[x]; i; i = e[i].net) {
int to = e[i].y;
if(to != fa) h[x] += son_num(to, x) + ;
}
return h[x];
} void everyson_to_one_dis(int x, int fa, int z) {
f[] += z;
for(int i = lin[x]; i; i = e[i].net) {
int to = e[i].y;
if(to != fa) everyson_to_one_dis(to, x, z + );
}
} void everyone_to_x_dis(int x, int fa) {
f[x] = f[fa] - (h[x] + ) + (n - h[x] - );
for(int i = lin[x]; i; i = e[i].net) {
int to = e[i].y;
if(to != fa) everyone_to_x_dis(to, x);
}
} int main() {
memset(lin, , sizeof(lin));
n = read();
for(int i = ; i < n; ++i) {
int x, y;
x = read(), y = read();
insert(x, y);
insert(y, x);
}
son_num(, );
for(int i = lin[]; i; i = e[i].net)
everyson_to_one_dis(e[i].y, , );
for(int i = lin[]; i; i = e[i].net)
everyone_to_x_dis(e[i].y, );
id = ;
for(int i = ; i <= n; ++i)
if(f[id] > f[i]) id = i;
cout << id << ' ' << f[id] << '\n';
return ;
}

最新文章

  1. 这些年一直记不住的 Java I/O
  2. 净捡软柿子捏--jQuery 遍历方法
  3. Yii 1开发日记 -- Ajax实现点击加载下一页
  4. POJ 3311 Hie with the Pie (状压DP)
  5. 深搜+DP剪枝 codevs 1047 邮票面值设计
  6. SQLAlchemy 对象缓存和刷新
  7. PostgreSQL Monitor pg_activity
  8. MySQL优化—工欲善其事,必先利其器之EXPLAIN
  9. *[topcoder]GooseTattarrattatDiv1
  10. [LeetCode#191]Number of Bits
  11. PagedList 分页
  12. c# 运算符 ?、??、?:
  13. 闲来瞎扯 -- 在vs2008下编写linux程序
  14. HTML5 画布参考
  15. 项目Alpha冲刺Day8
  16. leetcode(js)算法10之正则表达式匹配
  17. UVA11401-Triangle Counting-递推
  18. MySQL— 基础
  19. vue-router 与 react-router 设计理念上的区别
  20. 【LeetCode】Missing Ranges

热门文章

  1. Luogu3960 NOIP2017列队(splay/线段树)
  2. fzu 2246(ac 自动机)
  3. AOJ.602 大家来找茬
  4. 【BZOJ 4514】[Sdoi2016]数字配对 费用流
  5. Codeforces Round #348 (VK Cup 2016 Round 2, Div. 2 Edition) D
  6. Codeforces Round #526 (Div. 2) E. The Fair Nut and Strings
  7. centos关闭ipv6
  8. Linux下文件解压命令
  9. POST提交数据太大
  10. [POJ1595]欧拉线性筛(虽然这道题不需要...)