魔法师的技能树

题目内容

题目描述

在某个游戏中有一个魔法师角色,他的技能树上有n个不同的技能,被编号为0到n-1,除了初始技能外每个技能都需要学习了一个前置技能才可以学习,该技能也被称作其前置技能的子技能。技能树的根节点也就是初始技能是该角色被创建时就已经掌握了,而向一个分支学习直到没有子技能的时候,这个没有子技能的技能就被叫做终极技能。现在我们知道了所有技能之间的关系,请你求出初始技能的编号、子技能最多的技能编号、终极技能的数量和掌握各个技能分别最少需要学习多少个技能。

输入描述

第一行一个整数n,表示技能的总数。

接下来n-1行每行两个整数x和y,表示技能x是技能y的前置技能,输入保证不存在环。

其中n≤100,000

输出描述

第一行三个整数表示初始技能编号、子技能最多的技能编号和终极技能的数量,若子技能最多的技能有多个解则输出编号最小的一个。

第二行n个整数分别表示掌握每个技能分别最少需要学习多少个技能。

样例输入

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

样例输出

0 2 4 0 1 1 2 2 2 2 3

提示

读入数据存好树之后,依次求解即可。对于第二行,可以在bfs过程中求出树上每个节点的深度
提交评测
请登录后再操作

题目描述

魔法师的技能树
1607
0
13
5
38%
证书查询 x
请输入证书编号:

请输入正确的证书编号

学员姓名:孙兴民

课程:Scratch Level 1

发证日期:2019.08.15

证书查询

该证书不存在