K - Cosmic Playground 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

表示言語

/ /

Score : 100 points

Problem Statement

While exploring the galaxy, Navi and Hyeongtae discovered a cosmic playground! The cosmic playground consists of N points and N-1 bidirectional passages. Each point in the cosmic playground is numbered from 1 to N. The ith passage connects points u_i and v_i in both directions. It is always possible to travel between any two distinct points using only the passages. In other words, the cosmic playground has a tree structure.

Each point is connected to a single slide. For a permutation P=[P_1, P_2, \dots, P_N] of length N, sliding down the slide at point i moves you to point P_i.

Navi wants to slide down the slides non-stop to enjoy the thrill of speed. On the other hand, Hyeongtae is worried that if Navi travels too far, Navi might get lost in space. After much deliberation, Navi and Hyeongtae defined the risk level f(r) of point r as follows:

  • The distance between points a and b is the minimum number of passages one must traverse to reach point b from point a using only the passages.
  • Navi starts at point s and continues moving using only slides, while Hyeongtae watches Navi from point r. The maximum distance between point r and any point Navi can reach is defined as the maximum distance d(r, s).
  • The risk level f(r) when Hyeongtae remains at point r is the sum of the maximum distances \sum\limits_{s = 1}^{N}{d(r, s)} when Navi starts from each point.

Hyeongtae wants to stay at the point where the risk level is minimized. Let us help Hyeongtae by calculating the risk level for each point.

What is a permutation? A permutation of length N is a sequence that contains exactly one of each integer from 1 to N. For example, [2,1,4,3] is a permutation, but [4, 2, 1, 1] and [1, 2, 3, 5] are not.

Constraints

  • 3 \le N \le 100\,000
  • 1 \le u_i < v_i \le N
  • The given graph is a tree.
  • P is a permutation.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
P_1 P_2 \dots P_N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}

Output

Output N integers f(1), f(2), \dots, f(N), separated by spaces, where each integer represents the risk level of each point.

Sample Input 1

6
3 1 2 4 6 5
1 3
2 3
3 4
4 5
4 6

Sample Output 1

14 14 8 8 14 14

表示言語

/ /

점수 : 100 점

문제

은하계를 탐방하던 나비와 형태는 우주 놀이터를 발견했다! 우주 놀이터에는 N개의 포인트와 N-1개의 양방향 통로가 있다. 우주 놀이터의 각 포인트에는 1번부터 N번까지 번호가 순서대로 매겨져 있다. i번째 통로는 u_i번 포인트와 v_i번 포인트를 양방향으로 연결한다. 임의의 서로 다른 두 포인트를 통로만을 이용해 항상 오갈 수 있다. 즉 우주 놀이터는 트리 구조이다.

각 포인트에는 미끄럼틀이 하나씩 연결되어 있다. 길이 N의 순열 P = [P_1, P_2, \dots, P_N]에 대해 i번 포인트에서 미끄럼틀을 타면 P_i번 포인트로 이동한다.

나비는 속도감을 즐기기 위해 끊임없이 미끄럼틀을 타고 싶어 한다. 반면 형태는 너무 멀리 있는 포인트까지 이동했다가는 우주 미아가 될까 걱정이다. 나비와 형태는 열심히 고민한 결과 r번 포인트의 위험도 f(r)을 다음과 같이 정의했다.

  • a번 포인트와 b번 포인트 사이의 거리는 a번 포인트에서 통로만을 이용해 b번 포인트로 이동하기 위해 지나야 하는 통로의 최소 개수이다.
  • 나비는 s번 포인트에서 출발해 미끄럼틀만을 이용해 계속 이동하고, 형태는 r번 포인트에서 나비를 지켜본다. 이때 r번 포인트와 나비가 도달할 수 있는 포인트 사이의 거리 중 최댓값을 최대 거리 d(r, s)라고 한다.
  • 형태가 r번 포인트에 남아 있을 때의 위험도 f(r)은 나비가 각 포인트에서 출발했을 때의 최대 거리의 합 \sum\limits_{s = 1}^{N}{d(r, s)}이다.

형태는 위험도가 최소가 되는 포인트에 남아 있고자 한다. 형태를 도와 각 포인트의 위험도를 계산해 보자.

순열이란 길이가 N인 순열은 1부터 N까지의 정수가 정확히 한 번씩 등장하는 수열이다. 예를 들어 [2,1,4,3]은 순열이지만 [4,2,1,1]이나 [1,2,3,5]는 순열이 아니다.

제한

  • 3 \le N \le 100\,000
  • 1 \le u_i < v_i \le N
  • 주어지는 그래프는 트리 구조이다.
  • P는 순열이다.
  • 주어지는 모든 수는 정수이다.

입력

입력은 다음 형식으로 표준 입력으로 주어진다.

N
P_1 P_2 \dots P_N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}

출력

각 포인트의 위험도를 나타내는 N개의 정수 f(1), f(2), \dots, f(N)을 공백으로 구분하여 출력한다.

입력 예 1

6
3 1 2 4 6 5
1 3
2 3
3 4
4 5
4 6

출력 예 1

14 14 8 8 14 14

表示言語

/ /

配点 : 100 点

問題文

銀河を旅していたナビとヒョンテは，宇宙の遊び場を発見した！宇宙の遊び場には，N個のポイントとN-1個の双方向通路がある．宇宙の遊び場の各ポイントには，1番からN番までの番号が振られている．i番目の通路は，u_i番目のポイントとv_i番目のポイントを双方向に結んでいる．任意の異なる2つのポイントは，通路のみを利用して常に行き来することができる．つまり，宇宙の遊び場は木構造である．

各ポイントには，1つずつ滑り台が接続されている．長さNの順列P = [P_1, P_2, \dots, P_N]について，i番目のポイントから滑り台を滑ると，P_i番目のポイントへ移動する．

ナビはスピード感を味わうために，途切れることなく滑り台を滑り続けたいと思っている．一方，ヒョンテは，ナビがあまりにも遠いポイントまで移動してしまうと，宇宙で迷子になってしまうのではないかと心配している．ナビとヒョンテは一生懸命考えた結果，r番ポイントの危険度 f(r)を次のように定義した．

  • a番ポイントとb番ポイントの間の距離は，a番ポイントから通路のみを利用してb番ポイントへ移動するために通らなければならない通路の最小個数である．
  • ナビはs番目のポイントから出発し，滑り台のみを利用して移動を続け，ヒョンテはr番目のポイントからナビを見守る．このとき，r番目のポイントとナビが到達可能なポイントとの間の距離のうち，最大値を最大距離 d(r, s)と呼ぶ．
  • ヒョンテがr番ポイントに残っているときの危険度f(r)は，ナビが各ポイントから出発したときの最大距離の和 \sum\limits_{s = 1}^{N}{d(r, s)}である．

ヒョンテは危険度が最小になるポイントに残りたいと考えている．ヒョンテを助けて，各ポイントの危険度を計算してみよう．

順列とは 長さが N の順列とは、1 から N までの整数を、それぞれちょうど一つずつ含む数列である。例えば、[2,1,4,3] は順列だが、[4, 2, 1, 1] や [1, 2, 3, 5] は順列ではない。

制約

  • 3 \le N \le 100\,000
  • 1 \le u_i < v_i \le N
  • 与えられるグラフは木構造
  • Pは順列
  • 入力される数値はすべて整数

入力

入力は以下の形式で標準入力から与えられる．

N
P_1 P_2 \dots P_N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}

出力

各ポイントの危険度を表すN個の整数f(1), f(2), \dots, f(N)を空白区切りで出力せよ．

入力例 1

6
3 1 2 4 6 5
1 3
2 3
3 4
4 5
4 6

出力例 1

14 14 8 8 14 14