P26023

节点的信息

难度 5 级 图论算法 树上问题
讨论 统计 3通过 6提交 50%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

给定一个树,每个节点用1~n编号。求每个节点所在子树的节点数,及每个节点的深度

输入

输入第一行两个数n和r,r表示树的根。

接着n-1行,每行2个数字a,b。表示a和b之间有一条边。

输出

输出第2行,每行n个数,用空格分割。

第一行输出1~n节点深度

第二行输出1~n节点子树数量

样例

样例 1
输入
8 1
1 2
2 3
3 4
4 5
4 6 
2 7
7 8
输出
1 2 3 4 5 5 3 4
8 7 4 3 1 1 2 1

提示

n \leq 10^5

来源

原创

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交