35117번 - 생명의 샘

신비로운 정령의 숲에는 $N$개의 나무가 자라고 있다. 어떤 두 나무의 뿌리가 연결되는 지점이 $N - 1$개 존재하며, $i$번 지점에서는 $u_i$번 나무와 $v_i$번 나무가 연결된다. 또한, 이 나무들은 어떤 두 나무든 연결된 지점을 따라 서로에게 도달할 수 있다. 즉, 나무들의 연결 관계는 트리 구조를 이루고 있다.

각 나무 $i$는 고유한 생명력 수치 $A_i$를 가진다. 숲의 수호자는 숲 전체에 활력을 불어넣기 위해 $N$개의 나무 중 단 하나를 선택하여 해당 나무가 있는 곳을 생명의 샘으로 만들고자 한다. 생명의 샘을 만들게 되면, 생명의 물이 샘에서 시작하여 뿌리를 타고 다른 모든 나무로 퍼져 나간다. 이때 물의 흐름은 항상 생명의 샘에서 멀어지는 방향으로 흐른다. 이후, 숲의 수호자는 흐르는 물줄기를 이용해 공명을 일으킬 수 있다. 공명의 자세한 규칙은 다음과 같다.

• 공명은 물이 흐르는 경로상에 있는 두 나무, 상류의 나무와 하류의 나무를 마법으로 연결하여 발생시킨다. 두 나무가 직접 연결되어 있을 필요는 없다.
• 상류의 나무는 생명의 샘에 더 가까운 나무를 의미하며, 하류의 나무는 생명의 샘에서 더 먼 나무를 의미한다. 이때 생명의 샘에 있는 나무도 공명의 대상이 될 수 있다.
• 각 나무는 최대 하나의 공명에만 참여할 수 있다.
• 상류의 나무 $x$와 하류의 나무 $y$를 연결해 공명을 일으키면 $(A_y - A_x)$만큼의 마력 에너지가 생성된다.

숲의 수호자는 어떤 나무가 있는 곳을 생명의 샘으로 만들어야 숲 전체에서 생성되는 마력 에너지의 총합이 최대가 될지 알고 싶어한다. 숲의 수호자를 돕기 위해 모든 $1 \le i \le N$에 대하여, $i$번 나무가 있는 곳을 생명의 샘으로 선택했을 때 얻을 수 있는 최대 마력 에너지를 각각 구해보자.

첫째 줄에 나무의 개수 $N$이 주어진다. $(2 \le N \le 200\,000)$

둘째 줄에 각 나무의 생명력 수치 $A_1, A_2, \dots, A_N$이 공백으로 구분되어 주어진다. $\left(1 \le A_i \le 10^9\right)$

다음 $N - 1$개의 줄에 걸쳐, 서로 연결된 두 나무의 번호 $u_i, v_i$가 주어진다. $\left(1 \le u_i, v_i \le N\right)$

$1$번 나무부터 $N$번 나무까지, 각 나무가 있는 곳을 생명의 샘으로 만들었을 때 얻을 수 있는 최대 마력 에너지를 한 줄에 하나씩 출력한다.