#P9043. [2017年备战省选]b

    ID: 9249 传统题 2000ms 512MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2400提高+/省选-树重心排序贪心一维前缀和二分答案

[2017年备战省选]b

题目描述

一个王国的交通网络是一棵树。国王要选择一个到所有节点的距离和最小的节点。若有多个节点都使距离和最小,可以选择其中任意一个。

允许删去原树的一些边,再加入相同数量的边,使得到的图仍然是一棵树。对每个节点 ii,求最少要删去多少条原边,才能使 ii 成为可以被国王选中的节点。

输入格式

第一行一个正整数 nn,表示节点数。

接下来 n−1n-1 行,每行两个正整数 u,vu,v,表示节点 u,vu,v 之间的一条树边。

输出格式

输出 nn 行。第 ii 行一个整数,表示使节点 ii 可以被选中所需删去的最少原边数。

样例 1

10
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
0
4
4
4
4
4
4
4
4
4

原题的第二组样例见原比赛样例数据文件夹。

数据范围

测试点 nn
1–2 10
3–8 2000
9–14 100000
15–20 1000000

原 PDF 题面