Đếm cặp đỉnh

Trong chuyến nghỉ dưỡng tại Hawaii năm nay, các thành viên Big-Omega đã cùng nhau chơi một trò chơi như sau: Cho một đồ thị dạng cây gồm N đỉnh, $N - 1$ cạnh và một cặp số nguyên ($L, R$). Các đỉnh được đánh số từ 1 đến N, trong đó đỉnh 1 là gốc của cây. Mỗi đỉnh i mang một giá trị $v_i$. Với mỗi đỉnh u, gọi $d_u$ là số lượng giá trị $v_i$ phân biệt nằm trong cây con gốc u (tính cả u).

Hãy tính $count_u$ là số lượng cặp đỉnh $(x, y)\ (1 \leq x \lt y \leq N)$ thỏa mãn cả hai điều kiện sau:

• x và y nằm ở hai nhánh con khác nhau của u.
• $L \leq |d_x - d_y| \leq R$.

Tèo là một thành viên mới của Big-Omega năm nay. Để gây ấn tượng với mọi người trong công ty và giành giải thưởng, Tèo quyết tâm giải bằng được câu đố hóc búa này. Mặc dù không biết gì về lập trình, Tèo vẫn rất tự tin vì có một người bạn thân là lập trình viên chuyên nghiệp có thể giải quyết mọi bài toán khó nhằn. Bạn hãy giúp Tèo giải bài toán này thật nhanh nhé!

Đầu vào:

• Dòng đầu tiên chứa số nguyên dương N — số lượng đỉnh của cây ($1 \leq N \leq 10^5$).
• Dòng thứ hai chứa hai số nguyên L và R ($0 \leq L \leq R \leq N - 1$).
• Dòng thứ ba chứa N số nguyên dương $v_1, v_2, \dots, v_N$ — tương ứng là giá trị của các đỉnh ($1 \le v_i \le 10^9$).
• $N - 1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương u và v — mô tả một cạnh nối giữa hai đỉnh u và v trong cây ($1 \le u, v \le N, u \neq v$).
• Dữ liệu đầu vào đảm bảo tạo thành một cây hợp lệ.

Đầu ra:

• In ra trên một dòng duy nhất gồm N số nguyên $count_1\ count_2\ \dots\ count_N$ cách nhau bởi dấu cách — đại diện cho kết quả tại từng đỉnh.

Giải thích: Hình dưới đây minh họa cây trong ví dụ mẫu. Mỗi đỉnh được biểu diễn bởi hai thông số: chỉ số đỉnh / giá trị của đỉnh đó.

Theo hình minh họa, số lượng giá trị phân biệt trong cây con của mỗi đỉnh là:

• $d_1 = 7$ (Các giá trị trong cây con của đỉnh 1 lần lượt là 1, 2, 4, 6, 8, 9, 10).
• $d_2 = 1$ (10)
• $d_3 = 1$ (8)
• $d_4 = 1$ (9)
• $d_5 = 7$ (1, 2, 4, 6, 8, 9, 10)
• $d_6 = 4$ (2, 4, 8, 10)
• $d_7 = 1$ (4)
• $d_8 = 2$ (2, 4)
• $d_9 = 1$ (10)
• $d_{10} = 6$ (2, 4, 6, 8, 9, 10)

Giá trị $count_i$ tương ứng của mỗi đỉnh i:

• $count_1 = 8$: Gồm các cặp đỉnh (2, 3), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8), (2, 9), (2, 10). Mỗi cặp gồm hai đỉnh x, y nằm ở hai nhánh con khác nhau của đỉnh 1 và thỏa mãn $0 \leq |d_x - d_y| \leq 9$.
• $count_2 = count_3 = count_4 = count_5 = count_7 = count_8 = count_9 = 0$ vì các đỉnh này có không quá một nhánh con.
• $count_6 = 5$: Gồm các cặp đỉnh (3, 7), (3, 8), (3, 9), (7, 9), (8, 9).
• $count_{10} = 5$: Gồm các cặp đỉnh (3, 4), (4, 6), (4, 7), (4, 8), (4, 9).

Ví dụ 1:

Đầu vào:

10
0 9
4 10 8 9 1 8 4 2 10 6
10 4
9 6
3 6
6 10
5 1
2 1
5 10
6 8
8 7

Đầu ra:

8 0 0 0 0 5 0 0 0 5