호반우가 학교에 지각한 이유 7

마왕의 정체는 작년에 호반우가 키우던 애완용 트리였다. 트리는 여전히 어지러움을 느끼며 루트를 계속 바꾸고 있다. 이를 본 호반우는 트리의 루트로 신성한 물인 성수를 흘려보내 트리를 정화하려고 한다.

트리는 $N$개의 노드와 $N-1$개의 간선으로 이루어져 있으며, 각 노드는 $1$번부터 $N$번까지 번호가 정해져 있다. $1 \le i \le N$인 $i$에 대해 $i$번 노드는 양의 정수 $a_{i}$만큼 내부에 성수를 저장할 수 있는 공간을 가진다.

어떤 노드 $V$에 성수가 흘러 들어올 때 다음 규칙을 따른다.

1. $V$와 연결된 자식 노드로만 성수를 흘려보낼 수 있다.
2. 자식 노드가 없거나 모든 자식 노드의 내부가 성수로 가득 찼다면 $V$ 내부의 공간에 성수가 차기 시작한다.
3. $V$ 내부 공간의 크기가 $t$라면 공간을 가득 채우는 데 성수가 $t$만큼 필요하다.
4. 항상 $V$와 연결된 자식 노드 중 성수로 가득 차지 않은 노드들 가운데 번호가 가장 큰 노드와 가장 작은 노드에 같은 양의 성수를 동시에 흘려보낸다.
5. 규칙 4에서 번호가 가장 큰 노드와 가장 작은 노드가 같으면 해당 노드에만 성수를 흘려보낸다.
6. 성수를 흘려보내는 노드는 규칙 4에 따라 계속 유동적으로 바뀐다.
7. 성수는 매우 빠르게 흐르므로 흘러가는 시간은 무시한다. 즉 성수는 루트에 흘려보내자마자 채워야 할 공간에 바로 도착한다.

노드 $M$의 공간이 성수로 가득 차면 트리는 정화되며, 정화된 이후에는 더 이상 성수를 흘려보낼 수 없다.

루트가 계속 바뀌어 어지러워하는 호반우를 위해, 각 노드가 루트일 때 트리를 정화하는 데 필요한 성수의 양을 알려주자.

첫 번째 줄에 트리의 노드 개수 $N$과 성수로 가득 차야 할 노드 번호 $M$이 공백으로 구분되어 주어진다. ($1 \le M \le N \le 300\,000$)

두 번째 줄에 $N$개의 양의 정수 $a_{1}, a_{2}, \cdots, a_{N}$이 공백으로 구분되어 주어진다. ($1 \le a_{i} \le 10^{9}$) $a_{i}$는 $i$번 노드가 내부에 성수를 저장할 수 있는 공간의 크기이다.

세 번째 줄부터 $N-1$개의 줄에 걸쳐 트리의 각 간선이 연결하는 두 정점의 번호가 공백으로 주어진다.

$N$개의 줄에 걸쳐 답을 출력한다. $i$번째 줄에는 $i$번 노드가 루트일 때 트리를 정화하기 위해 루트로 흘려보낼 성수의 양을 출력한다.

입출력의 양이 많으므로 빠른 입출력을 사용하는 것을 권장합니다. 언어별 빠른 입출력 방법은 아래를 참고하세요.

• C++: cin, cout을 사용하는 경우 입출력 전에 cin.tie(nullptr); ios::sync_with_stdio(false);를 한 번 적용해야 합니다. 줄을 바꿀 때는 endl 대신 '\n'을 사용해야 합니다.
• Java: BufferedReader와 BufferedWriter를 사용해야 합니다.
• Python3, PyPy3: input() 대신 sys.stdin.readline().rstrip()을 사용해야 합니다.