#6042. 「雅礼集训 2017 Day7」跳蚤王国的宰相

内存限制:1024 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

跳蚤王国爆发了一场动乱,国王在镇压动乱的同时,需要在跳蚤国地方钦定一个人来做宰相。

由于当时形势的复杂性,很多跳蚤都并不想去做一个傀儡宰相,带着宰相的帽子,最后还冒着被打倒并杀头的危险,然而有一只跳蚤却想得与众不同最时尚。

本来他打算去教书,他已经发表了自己在学术方面的见解,获得了很多跳蚤们的赞同,但是这时听说跳蚤国要钦定宰相,他毅然打断了想去教书的想法,他觉得只要为了国家利益,自己的生死都可以不管,哪里能因为工作能给自己带来灾祸或者福分就去避开或者接近这份工作呢?所以他决定站出来接了这份工作。

然而当时国王的钦定方式很奇怪,跳蚤王国可以看作一棵树,国王认为宰相必须更好的为跳蚤服务,所以他会选择一个到所有节点距离和最小的节点,并在这个节点中钦定,如果有多个节点满足距离和最小则任选一个。

然而跳蚤国的动乱实在是太厉害了,以至于树的形态可能也会发生改变,也就是说,树上可能会有若干条边消失,如果这个情况出现的话一定会有同样数目的边出现,以保证整个结构仍然是一棵树

现在这个跳蚤想知道每个节点中的跳蚤如果要被钦定,至少需要多少条边消失(当然也会有同样数目的边出现)。作为这只跳蚤的一名真正的粉丝,你能帮他解决这个问题吗?

输入格式

第一行一个正整数 n 表示树中点的个数。
接下来 n - 1 行,每行两个正整数 u v ,表示点 u 与点 v 之间有一条树边。

输出格式

输出 n 行,第 i 行一个数,表示第 i 个节点如果要被钦定至少需要多少条边消失。

样例

样例输入 1

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

样例输出 1

0
4
4
4
4
4
4
4
4
4

数据范围与提示

对于 10\% 的数据, n \leq 10
对于 40\% 的数据, n \leq 2000
对于 70\% 的数据, n \leq 100000
对于 100\% 的数据, 10 \leq n \leq 1000000