链接:青出于蓝胜于蓝
Description
- 武当派一共有 n 人,门派内 n 人按照武功高低进行排名,武功最高的人排名第 1,次高的人排名第 2,…武功最低的人排名第 n。现
- 在我们用武功的排名来给每个人标号,除了祖师爷,每个人都有一个师父,每个人可能有多个徒弟。
- 我们知道,武当派人才辈出,连祖师爷的武功都只能排行到 p。也就是说徒弟的武功是可能超过师父的,所谓的青出于蓝胜于蓝。
- 请你帮忙计算每个人的所有子弟(包括徒弟的徒弟,徒弟的徒弟的徒弟….)中,有多少人的武功超过了他自己。
Input
- 输入第一行两个整数 n,p(1≤n≤100000,1≤p≤n)。
- 接下来 n−1 行,每行输入两个整数u,v(1≤u,v≤n),表示 u 和 v 之间存在师徒关系。
Output
- 输出一行 n 个整数,第 i 个整数表示武功排行为 i 的人的子弟有多少人超过了他。行末不要输出多余的空格。
Sample Input
10 5
5 3
5 8
3 4
3 1
2 1
6 7
8 7
9 8
8 10Sample Output
0 0 2 0 4 0 1 2 0 0题解
- 树状数组维护dfs的时间戳,每访问一个点,in数组标记他,标记完所有子树的节点后,out数组取消标记
- 然后这个点的答案就是out[u]到in[u]区间内的和
1 |
|