Hẹn hò

Có $n$ ngôi nhà được đánh số từ $1$ đến $n$, được nối với nhau bởi $n-1$ con đường hai chiều sao cho tạo thành một cây (giữa hai ngôi nhà bất kỳ có đúng một đường đi đơn).

Mỗi ngôi nhà $i$ có hai thuộc tính:

• Giới tính $g_i\in \{0,1\}$ (giá trị $1$ là con trai, giá trị $0$ là con gái).
• Số yêu thích $f_i$ ($1\le f_i\le {10}^9$).

Cho $q$ truy vấn, mỗi truy vấn gồm hai số $a$ và $b$. Với mỗi truy vấn, hãy đếm số cặp không có thứ tự $(u,v)$ sao cho cả $u$ và $v$ đều nằm trên đường đi đơn từ $a$ đến $b$, đồng thời $g_u\ne g_v$ và $f_u=f_v$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ ($1\le n\le {10}^5$).
• Dòng thứ hai chứa $n$ số nguyên $g_1,g_2,\dots ,g_n$, mỗi số là $0$ hoặc $1$.
• Dòng thứ ba chứa $n$ số nguyên $f_1,f_2,\dots ,f_n$ ($1\le f_i\le {10}^9$).
• $n-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a_i$ và $b_i$ ($1\le a_i,b_i\le n$) mô tả một cạnh của cây.
• Dòng tiếp theo chứa số nguyên $q$ ($1\le q\le {10}^5$).
• $q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a$ và $b$ ($1\le a,b\le n$) mô tả một truy vấn.

Dữ liệu ra

In ra $q$ dòng, mỗi dòng là đáp án của một truy vấn theo thứ tự đề bài.

Ràng buộc

• $1\le n,q\le {10}^5$
• $1\le f_i\le {10}^9$
• Đồ thị đề bài cho là một cây liên thông.

Ví dụ