← 返回题目列表

AtCoder · codequeen2023_final_c

C. 路径交叉点

中文机器翻译题面 查看原题

配点: 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 。