表示言語
/ /分数: 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