25337번 - Merge the Tree and Sequence

정휘는 정점이 $N$개인 트리와 길이가 $N$인 수열을 갖고 있다. 트리의 각 정점에는 정수가 하나씩 적혀 있으며, 각 간선은 1 이상 20만 이하의 자연수로 표현되는 색깔 중 하나로 칠해져 있다.

정휘는 트리와 수열을 따로 구분해야 하는 게 귀찮아서, 트리의 정점과 수열의 원소를 일대일대응시키는 방식으로 트리와 수열을 합치기로 했다. 물론 그냥 합치는 건 재미가 없으니, 트리와 수열을 합칠 때의 점수를 아래와 같이 정의하기로 했다.

• 아래 조건을 만족하도록 트리의 간선들을 1개 이상의 구역으로 나눈다. 아래 방식으로 트리를 나누는 방법은 유일하다.
  • 트리의 모든 간선은 정확히 하나의 구역에 속한다.
  • 모든 구역은 적어도 1개 이상의 간선을 포함한다.
  • 만약 한 끝점을 공유하는 두 간선의 색깔이 같다면 두 간선은 같은 구역에 속한다.
• 어떤 구역의 점수는 (구역에 속한 간선들의 끝점에 적힌 수의 합) × (구역에 속한 간선들의 끝점에 대응되는 수열의 원소의 합)으로 정의된다.
• 트리와 수열을 합칠 때의 점수는 모든 구역의 점수를 더한 값이다.

예를 들어, 아래 트리는 4개의 구역으로 나누어진다.

그리고, 만약 정휘가 아래와 같은 방식으로 수열과 트리를 합친다면, 아래와 같은 102점을 얻게 된다.

정휘는 트리와 수열을 합칠 때 얻을 수 있는 점수의 최솟값과 최댓값이 궁금해졌지만, 트리와 수열의 크기가 너무 커서 계산하지 못하고 있다. 컴퓨터를 잘 다루는 여러분들이 정휘를 도와 얻을 수 있는 점수의 최솟값과 최댓값을 구해보자.

첫째 줄에 트리의 정점의 개수와 수열의 길이를 의미하는 정수 $N$이 주어진다. ($2 \leq N \leq 200\,000$)

둘째 줄부터 $N-1$개의 줄에 걸쳐, 트리의 간선을 의미하는 세 정수 $v_i, w_i, c_i$가 한 줄에 하나씩 공백으로 구분되어 주어진다. 이는 $v_i$번 정점과 $w_i$번 정점을 연결하는 간선의 색깔이 $c_i$라는 것을 의미한다. ($1 \leq v_i, w_i \leq N$, $1 \leq c_i \leq 200\,000$)

다음 줄에는 트리의 $1, 2, \cdots, N$번 정점에 적힌 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. ($-1\,000 \leq A_i \leq 1\,000$)

다음 줄에는 길이가 $N$인 수열의 원소를 나타내는 정수 $B_1, B_2, \cdots, B_N$이 공백으로 구분되어 주어진다. ($-1\,000 \leq B_i \leq 1\,000$)

첫째 줄에 정휘가 얻을 수 있는 점수의 최솟값을 출력한다.

둘째 줄에 정휘가 얻을 수 있는 점수의 최댓값을 출력한다.

• 정답이 32비트 정수 범위를 넘을 수 있다.