Merge the Tree and Sequence

Jeonghwi has a tree with $N$ vertices and a sequence of length $N$. Each vertex of the tree has one integer written on it, and each edge is painted with one of the colors, which are natural numbers from 1 to 200,000.

Jeonghwi finds it tedious to keep the tree and the sequence separate, so he decided to merge them by matching the vertices of the tree one-to-one with the elements of the sequence. Merging them without any twist would be dull, so he defined the score of a merge as follows.

• Split the edges of the tree into one or more regions that satisfy the conditions below. The way to split the tree in this manner is unique.

  • Every edge of the tree belongs to exactly one region.
  • Every region contains at least one edge.
  • If two edges sharing an endpoint have the same color, the two edges belong to the same region.

• The score of a region is (the sum of the integers written on the endpoints of the edges in the region) × (the sum of the sequence elements matched to the endpoints of the edges in the region).

• The score of a merge is the sum of the scores of all regions.

For example, the tree below is split into 4 regions.

If Jeonghwi merges the sequence and the tree as shown below, he gets 102 points.

Jeonghwi wants to know the minimum and maximum scores he can get when merging the tree and the sequence, but the tree and the sequence are too large for him to compute by hand. Help Jeonghwi find the minimum and maximum scores he can get.

The first line contains the integer $N$, the number of vertices in the tree and the length of the sequence. ($2 \leq N \leq 200\,000$)

From the second line to the $N$-th line, each of the next $N-1$ lines contains three integers $v_i, w_i, c_i$ separated by spaces. This means that the edge connecting vertex $v_i$ and vertex $w_i$ has color $c_i$. ($1 \leq v_i, w_i \leq N$, $1 \leq c_i \leq 200\,000$)

The next line contains the integers $A_1, A_2, \cdots, A_N$ written on vertices $1, 2, \cdots, N$ of the tree, separated by spaces. ($-1\,000 \leq A_i \leq 1\,000$)

The next line contains the integers $B_1, B_2, \cdots, B_N$, the elements of the sequence of length $N$, separated by spaces. ($-1\,000 \leq B_i \leq 1\,000$)

On the first line, print the minimum score Jeonghwi can get.

On the second line, print the maximum score Jeonghwi can get.

• The answer can exceed the range of a 32-bit integer.