Số Màu Trong Mỗi Cây Con · canuc80k3116

Cho một cây gồm $n$ đỉnh, gốc tại đỉnh $1$ . Mỗi đỉnh $i$ được gán một màu $c_{i}$ ; nhiều đỉnh có thể có cùng màu.

Với từng đỉnh $v$ , hãy đếm số giá trị màu khác nhau xuất hiện trong cây con gốc $v$ , có tính cả màu của chính $v$ .

Input

Dòng đầu chứa số nguyên $n$ .
Dòng thứ hai chứa $n$ số nguyên $c_{1}, c_{2}, \dots, c_{n}$ .
Mỗi dòng trong $n - 1$ dòng tiếp theo chứa hai số $u, v$ , biểu diễn một cạnh của cây.

Output

In $n$ số nguyên trên một dòng. Số thứ $v$ là số màu khác nhau trong cây con của đỉnh $v$ .

Constraints

$1 \leq n \leq 2 \cdot 1 0^{5}$ .
$1 \leq c_{i} \leq 1 0^{9}$ .
$1 \leq u, v \leq n, u \neq = v$ .
Các cạnh tạo thành một cây.

Scoring

Subtask $1$ ( $50%$ số điểm): $n \leq 2000$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

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

Output

4 2 3 1 1 2 1 1

Giải thích: Toàn cây dùng bốn màu. Cây con của $2$ có các màu $2, 3, 2$ nên có hai màu khác nhau; cây con của $3$ có các màu $1, 3, 3, 4$ nên có ba màu.

Nhận xét: Euler preorder biến cây con v thành đoạn [tin[v],tout[v]] của mảng màu. Ta cần trả số giá trị phân biệt cho n đoạn có đầu phải đã biết.
Thuật toán: Quét mảng Euler từ trái sang phải. Fenwick tree luôn đặt đúng một dấu 1 tại vị trí xuất hiện cuối cùng của mỗi màu trong prefix hiện tại: trước khi thêm vị trí mới, xóa dấu ở lần xuất hiện trước của màu đó. Khi quét tới tout[v], tổng Fenwick trên [tin[v],tout[v]] là đáp án của v.
Chứng minh tính đúng đắn: Với mỗi màu, dấu 1 duy nhất nằm tại lần xuất hiện cuối không vượt đầu phải đang xét. Màu ấy xuất hiện trong đoạn [l,r] khi và chỉ khi dấu đó nằm không nhỏ hơn l. Vì đoạn Euler là đúng cây con, tổng dấu trong đoạn đếm chính xác số màu phân biệt.
Độ phức tạp: O(n log n) thời gian và O(n) bộ nhớ.