C - Path Intersection Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

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