Escape Through Leaf

노드 1을 루트로 하는, n개의 노드(1부터 n까지 번호가 매겨짐)로 이루어진 트리가 주어진다. 또한 각 노드에는 두 값이 연결되어 있다. i-th번째 노드의 값은 ai와 bi이다.

한 노드에서 그 노드의 부분 트리에 있는 임의의 노드로 점프할 수 있다. 노드 x에서 노드 y로 한 번 점프하는 비용은 ax와 by의 곱이다. 한 번 이상의 점프로 이루어진 경로의 총비용은 각 점프 비용의 합이다. 모든 노드에 대해, 그 노드에서 임의의 리프에 도달하기 위한 최소 총비용을 계산한다. 루트는 차수가 1이더라도 절대로 리프가 될 수 없음에 유의한다.

한 노드에서 자기 자신으로 점프할 수 없음에 유의한다.

입력의 첫 번째 줄에는 트리의 노드 수를 나타내는 정수 n (2 ≤ n ≤ 105)이 주어진다.

두 번째 줄에는 공백으로 구분된 n개의 정수 a1, a2, ..., an( - 105 ≤ ai ≤ 105)이 주어진다.

세 번째 줄에는 공백으로 구분된 n개의 정수 b1, b2, ..., bn( - 105 ≤ bi ≤ 105)이 주어진다.

다음 n - 1개의 줄에는 트리에서 노드 ui와 vi 사이의 간선을 나타내는, 공백으로 구분된 두 정수 ui와 vi (1 ≤ ui, vi ≤ n)이 주어진다.

공백으로 구분된 n개의 정수를 출력한다. 이 중 i-th번째 정수는 노드 i에서 임의의 리프에 도달하는 경로의 최소 비용을 나타낸다.

첫 번째 예제에서 노드 3은 이미 리프이므로 비용은 0이다. 노드 2에서는 비용 a2 × b3 = 50으로 노드 3으로 점프한다. 노드 1에서는 비용 a1 × b3 = 10으로 노드 3으로 바로 점프한다.

두 번째 예제에서 노드 3과 노드 4는 리프이므로 비용은 0이다. 노드 2에서는 비용 a2 × b4 = 100으로 노드 4로 점프한다. 노드 1에서는 비용 a1 × b2 = - 400으로 노드 2로 점프한 다음, 비용 a2 × b4 = 100으로 2에서 4로 점프한다.