配点: 400 点
問題文
在顶部 编号为 1, 2, \ldots, N 它有多个 N 顶点树和顶点数 给出了 S, T 。i = 1, 2, \ldots, N-1 , 当我输入i 第一条边是顶点 u_i 和边 v_i 是平局。
树的每个顶点 请回答以下有关 j 的问题。
- 頂点 S 到顶点 到 j 的最短路径中包含的顶点(顶点)集合 S 和顶点 j ) 和顶点 有多少个顶点同时属于 T 到顶点 到 j 的最短路径中包含的顶点(顶点)集合 T 和顶点 j )?
制約
- 所有输入均以整数形式给出
- 3 \leq N \leq 200{,}000
- 1 \leq S, T \leq N
- S \neq T
- 1 \leq u_i, v_i \leq N (1 \leq i \leq N-1)
- 给定的图是一棵树 请输出
入力
输入是按以下格式从标准输入给出的。
N S T
u_1 v_1
\vdots
u_{N-1} v_{N-1}
出力
N 行。
i 行包含顶点 请输出有关 i 问题的答案。
入力例
11 1 4 1 2 2 3 3 5 3 6 2 4 4 7 1 8 8 9 8 10 9 11
出力例
1 1 2 1 3 3 2 2 3 3 4
在此输入示例中, 当S = 1, T = 4 。
- j = 1 到
- S 减去 j 的最短路径中包含的顶点集是 \left\{ 1 \right\} 。
- T 减去 j 的最短路径中包含的顶点集是 \left\{ 1, 2, 4 \right\} 。
- 两者都属于顶点 由于只有 1 ,所以答案是 1 。
- j = 5 到
- S 减去 j 的最短路径中包含的顶点集是 \left\{ 1, 2, 3, 5 \right\} 。
- T 减去 j 的最短路径中包含的顶点集是 \left\{ 2, 3, 4, 5 \right\} 。
- 两者都属于顶点 由于只有 2, 3, 5 所以答案是 3 。