生活在树上
题号:NC232359
时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

ZHR 住在一有根棵树上(1 号节点为根),树上的每条边都有一个距离。由于他特别懒,所以他一天移动的距离不能超过 2,对于每个节点,问他在一天中可以通过这个节点到达多少个不同的节点。

输入描述:

第一行一个 n 表示树的节点数量。
接下来 n-1 行,第 i 行两个数 f_iw_i,分别表示这个点的父亲和它到父亲的距离。

输出描述:

n 行,第 i 行表示从 i 节点出发能到达多少不同的节点。
示例1

输入

复制
5
1 2
1 1
2 1
3 3

输出

复制
3
3
2
2
1