問題一覧 > 通常問題

No.1817 Reversed Edges

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 125
作問者 : nok0nok0 / テスター : kichi2004_kichi2004_ rianoriano
6 ProblemId : 7543 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-01-21 23:34:40

問題文

$N$ 頂点からなる木が与えられます。

頂点には $1$ から $N$ の、辺には $1$ から $N-1$ の番号がついており、辺 $i$ は頂点 $A_i$ と $B_i$ を双方向に結んでいます。

頂点 $x$ の 逆張り度を以下で定義します。

  • 頂点 $x$ を根とし、頂点 $x$ から遠ざかる向きに木の各辺を向き付けする。このように向き付けして得られる各有向辺 $i$ の始点を $s_i$ 、終点を $t_i$ としたときに、 $s_i > t_i$ を満たす $i$ の個数を頂点 $x$ の逆張り度と定義する。

頂点 $1,2,\dots,N$ の逆張り度を求めてください。

制約

  • 入力は全て整数である。
  • $2 \le N \le 10^5$
  • $1 \le A_i,B_i \le N$
  • 与えられるグラフは木である。

入力

$N$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_{N-1}$ $B_{N-1}$

出力

$i\ (1\le i \le N)$ 行目に頂点 $i$ の逆張り度を出力してください。

サンプル

サンプル1
入力
3
1 2
2 3
出力
0
1
2

頂点 $1$ の逆張り度を考えます。頂点 $1$ から遠ざかる向きに辺を向き付けすると、辺 $1$ は頂点 $1$ から $2$ への有向辺となり、辺 $2$ は頂点 $2$ から $3$ への有向辺となります。始点の番号が終点の番号より大きい辺の本数は $0$ なので、頂点 $1$ の逆張り度は $0$ です。

頂点 $2$ の逆張り度を考えます。頂点 $2$ から遠ざかる向きに辺を向き付けすると、辺 $1$ は頂点 $2$ から $1$ への有向辺となり、辺 $2$ は頂点 $2$ から $3$ への有向辺となります。始点の番号が終点の番号より大きい辺の本数は $1$ なので、頂点 $2$ の逆張り度は $1$ です。

頂点 $3$ の逆張り度を考えます。頂点 $3$ から遠ざかる向きに辺を向き付けすると、辺 $1$ は頂点 $2$ から $1$ への有向辺となり、辺 $2$ は頂点 $3$ から $2$ への有向辺となります。始点の番号が終点の番号より大きい辺の本数は $2$ なので、頂点 $3$ の逆張り度は $2$ です。

サンプル2
入力
5
1 2
1 4
2 3
2 5
出力
0
1
2
1
2

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。