No.1817 Reversed Edges

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

No.1817 Reversed Edges

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 146
作問者 :

nok0 / テスター :

kichi2004_

riano

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 \leq N \leq 10^{5}$
$1 \leq A_{i}, B_{i} \leq N$
与えられるグラフは木である。

入力

 $N$ 
 $A_{1}$   $B_{1}$ 
 $A_{2}$   $B_{2}$ 
 $⋮$ 
 $A_{N - 1}$   $B_{N - 1}$

出力

$i (1 \leq i \leq 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

入力

出力

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

yukicoder

No.1817 Reversed Edges

問題文

制約

入力

出力

サンプル

サンプル1

入力

出力

サンプル2

入力

出力