146. 传送树
内存限制:256 MB
时间限制:1.000 S
题目描述
小红有一棵传送树,树上有 n (1 <= n <= 10^5) 个节点,编号为 1 到 n,其中 1 号节点为根节点。
每个节点都有一个传送门,传送门只可以将小红传送到子树中除了自己的其他节点中编号最小的节点。
小红想知道,经过若干次传送门直到叶子节点为止,可以到达的节点数量是多少。
输入
一行一个整数 n,表示树上的节点数量接下来 n - 1 行,每行两个整数 u, v,表示 u 号节点和 v 号节点之间有一条边(u 指向 v)。
输出
输出一行,n 个整数,分别对树上 n 个节点都需要计算答案,第 i 数字表示小红从第 i 个节点出发,经过若干次传送门到达叶子节点为止,可以到达的节点数量是多少。
样例输入 复制
5
1 4
4 2
4 3
3 5
样例输出 复制
2 1 2 2 1
提示
节点1 在其子树,除了自己 最小的节点是 节点2,节点1 传送门到 节点2.
从节点1出发到达叶子节点经过的节点数量是2 , 分别是节点 1 和 节点2
节点2 在其子树,除了自己最小的节点 就是节点2,节点2 传送门到 节点2.
从节点2出发到达叶子节点经过的节点数量是1 ,只是节点2
节点3 在其子树中 除了自己最小的节点 就是节点5,节点3 传送门到 节点5.
从节点3出发到达叶子节点经过的节点数量是2 ,分别是 节点3 和 节点5
意思类推,最后答案是:2 1 2 2 1