← 返回题目列表

AtCoder · scpc2026_div2_k

K. 宇宙游乐场

中文机器翻译题面 查看原题

表示言語

/ /

分数: 100 点

问题陈述

在探索银河系时,Navi 和 Hyeongtae 发现了一个宇宙游乐场!宇宙游乐场由……组成 N 点和 N-1 双向的 通道。宇宙游乐场中的每一个点都编号从 1 to N。的 ith 通道 连接点 u_i 和 v_i 在两个方向上都是如此。总是可以仅使用 通道在任意两个不同的点之间旅行。换句话说,这个宇宙游乐场具有树状结构。

每个点都连接到一个单独的 滑梯。对于一个排列 P=[P_1, P_2, \dots, P_N] 长度 N,向下滑动 滑梯 在点 i 会将你移到 P_i.

点。Navi想要滑下 滑道。 不停地享受速度的刺激。另一方面,Hyeongtae 担心如果 Navi 旅行得太远,Navi 可能会在太空中迷路。经过多次考虑,Navi 和 Hyeongtae 定义了 风险等级 f(r) 点 r 如下:

  • 的 距离 点与点之间 a 和 b 是必须经过的最少 通道 数量才能到达该点。 b 从点 a 仅使用 通道.
  • ,Navi 从点 s 开始,并仅使用 滑道。继续移动,而 Hyeongtae 从点 r观看 Navi。点之间的最大距离 r 和 Navi 可以到达的任何点被定义为 最大距离 d(r, s).
  • 的 风险等级 f(r) 当 Hyeongtae 保持在点 r 是从每个点开始时 Navi 的最大距离之和 \sum\limits_{s = 1}^{N}{d(r, s)} 。

亨泰想要停留在风险等级最小的点。让我们通过计算每个点的风险等级来帮助亨泰。

什么是排列? A 排列 长度 N 是一个包含每个整数恰好一次的序列 1 to 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번 포인트를 양방향으로 연결한다. 임의의 서로 다른 두 포인트를 통로만을 이용해 항상 오갈 수 있다. 즉 우주 놀이터는 트리 구조이다.

각 포인트에는 미끄럼틀이 하나씩 연결되어 있다. 길이 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