Phòng ban

Một công ty công nghệ có \(N\) phòng ban được tổ chức theo dạng cấu trúc cây, với phòng ban số \(1\) là gốc của cây. Mỗi phòng ban tương ứng với một đỉnh của cây. Phòng ban \(i\) có hai thông số đặc trưng:

• \(a(i)\): Loại hình hoạt động chính của phòng ban.
• \(b(i)\): Số điểm tài nguyên mà phòng ban có được.

Giám đốc điều hành muốn tối ưu hóa hiệu suất làm việc của từng phòng ban. Nhiệm vụ là, với mỗi phòng ban \(i\), hãy tìm giá trị \(f(u, v)\) lớn nhất giữa hai phòng ban \(u\) và \(v\) nằm trong cây con có gốc là phòng ban \(i\), sao cho phòng ban \(i\) là tổ tiên chung gần nhất của \(u\) và \(v\). Giá trị \(f(u, v)\) được định nghĩa như sau:

$
f(u, v) =
\begin{cases}
0 & \text{nếu } a(u) \neq a(v), \
\sum b(x) & \text{với } x \text{ là các phòng ban nằm trên đường đi từ } u \text{ đến } v.
\end{cases}
$

Lưu ý:

• \(lca(u, v) = i\) khi và chỉ khi phòng ban \(i\) là tổ tiên chung gần nhất và là tổ tiên sâu nhất của cả hai phòng ban \(u\) và \(v\).
• Đường đi từ \(u\) đến \(v\) bao gồm tất cả các phòng ban trên cây từ \(u\) đến \(v\).

Input

• Dòng đầu tiên chứa số nguyên \(N\) \((1 \leq N \leq 10^5)\), số lượng đỉnh trong cây.
• Dòng thứ hai chứa \(N\) số nguyên \(a(1), a(2), \ldots, a(N)\) \((1 \leq a(i) \leq 10^9)\).
• Dòng thứ ba chứa \(N\) số nguyên \(b(1), b(2), \ldots, b(N)\) \((0 \leq b(i) \leq 10^9)\).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) \((1 \leq u, v \leq N)\), biểu diễn cạnh nối giữa hai đỉnh \(u\) và \(v\) trong cây.

Output

Với mỗi \(i\) \((1 \leq i \leq N)\), hãy tìm giá trị lớn nhất của \(f(u, v)\) với \(u, v\) là hai phòng ban nằm trong cây con có gốc tại \(i\).

Example

8
2 2 3 3 5 2 3 1
5 4 1 3 1 8 1 5
1 3
4 6
8 4
2 3
4 3
1 5
7 5

17 0 16 0 0 0 0 0 

Scoring

• Có \(30\%\) số test ứng với \(n \le 1000\)
• Có \(20\%\) số test ứng với \(a(i) \le 10\)
• \(50\%\) số test còn lại không có ràng buộc gì thêm.