問題一覧 > 通常問題

No.1817 Reversed Edges

レベル : / AI推定難易度 : 925 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 154
作問者 : nok0 / テスター : kichi2004_ riano
お気に入りにしたユーザー ProblemId : 7543 / 自分の提出
問題文最終更新日: 2022-01-21 23:34:40
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 328 (順位表) の他の問題:

Problem Statement

You are given a tree with $N$ vertices.

The vertices are numbered from $1$ to $N$ and the edges are numbered from $1$ to $N-1$. Edge $i$ bidirectionally connects vertices $A_i$ and $B_i$.

The contrarian degree of a vertex $x$ is defined as follows.

  • Root the tree at vertex $x$ and orient each edge of the tree in the direction away from vertex $x$. Let $s_i$ be the start point and $t_i$ the end point of each directed edge $i$ obtained by this orientation. The contrarian degree of vertex $x$ is defined as the number of $i$ satisfying $s_i > t_i$.

Find the contrarian degrees of vertices $1,2,\dots,N$.

Constraints

  • All inputs are integers.
  • $2 \le N \le 10^5$
  • $1 \le A_i,B_i \le N$
  • The given graph is a tree.

Input

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

Output

On the $i\ (1\le i \le N)$-th line, output the contrarian degree of vertex $i$.

Sample

Sample 1
Input
3
1 2
2 3
Output
0
1
2

Consider the contrarian degree of vertex $1$. Orienting the edges away from vertex $1$, edge $1$ becomes a directed edge from vertex $1$ to $2$, and edge $2$ becomes a directed edge from vertex $2$ to $3$. The number of edges whose start point has a larger number than its end point is $0$, so the contrarian degree of vertex $1$ is $0$.

Consider the contrarian degree of vertex $2$. Orienting the edges away from vertex $2$, edge $1$ becomes a directed edge from vertex $2$ to $1$, and edge $2$ becomes a directed edge from vertex $2$ to $3$. The number of edges whose start point has a larger number than its end point is $1$, so the contrarian degree of vertex $2$ is $1$.

Consider the contrarian degree of vertex $3$. Orienting the edges away from vertex $3$, edge $1$ becomes a directed edge from vertex $2$ to $1$, and edge $2$ becomes a directed edge from vertex $3$ to $2$. The number of edges whose start point has a larger number than its end point is $2$, so the contrarian degree of vertex $3$ is $2$.

Sample 2
Input
5
1 2
1 4
2 3
2 5
Output
0
1
2
1
2

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