No.1817 Reversed Edges
タグ : / 解いたユーザー数 145
作問者 :
nok0
/ テスター :
kichi2004_
riano
問題文
$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もしくは右上の雲マークをクリックしてアカウントを作成してください。