問題一覧 > 通常問題

No.1817 Reversed Edges

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

問題文

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

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

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

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

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

制約

  • 入力は全て整数である。
  • 2N105
  • 1Ai,BiN
  • 与えられるグラフは木である。

入力

N
A1 B1
A2 B2

AN1 BN1

出力

i (1iN) 行目に頂点 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もしくは右上の雲マークをクリックしてアカウントを作成してください。