| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 112 | 63 | 54 | 61.364% |
$N$개의 정점으로 이루어진 트리 $T$가 주어진다. 당신은 $T$의 각 정점 $i (1 \leq i \leq N)$에 $1$이상 $N$이하의 서로 다른 수 $P(i)$를 배정하려고 한다. 즉, $P$가 순열이 되게 수를 배정한다.
어떤 정점 $v$에 대해, 인접한 정점들을 $\left\{ u_1, \, u_2, \, \cdots, \, u_k \right\}$라 하자. 이때, 정점 $v$에 배정된 값 $P(v)$가 집합 $\{P(v), P(u_1), P(u_2), \cdots, P(u_k) \}$의 중앙값이라면 ($P(v)$ 가 포함됨에 유의하라), 정점 $v$를 보통의 정점이라 한다. 모든 정점이 보통의 정점이 되도록 순열 $P$를 구성하자.
원소가 $k$개 있는 집합을 오름차순으로 정렬했을 때,
첫 번째 줄에 $N$이 주어진다. ($2 \leq N \leq 100 \,000$)
두 번째 줄부터 $N-1$개의 줄에 걸쳐 트리의 간선 $u, v$가 공백으로 구분되어 주어진다. ($1 \leq u, v \leq N$)
첫 번째 줄에 $N$개의 수를 공백으로 구분하여 출력하라. $i (1 \leq i \leq N)$번째 수는 정점 $i$에 적힌 수 $P(i)$이다. $P$는 순열이어야 한다.
5 1 2 2 3 2 5 1 4
2 4 5 1 3
위 예제는 아래 그림과 같다.
School > 경기과학고등학교 > 나는코더다 송년대회 > 나는코더다 2025 송년대회 G번