Cho một cây gồm \(N\) đỉnh và \(N - 1\) cạnh vô hướng. Các đỉnh được đánh số từ \(1\) đến \(N\), mỗi đỉnh \(u\) ban đầu có một trọng số cố định là \(W\lbrack u\rbrack\). Ban đầu, tất cả các đỉnh trên cây đều có màu Trắng. Bạn cần xử lý \(Q\) truy vấn thuộc hai loại:

• \(1\ u\): Đổi màu của đỉnh \(u\) từ Trắng sang Đen (nếu đỉnh \(u\) đã có màu Đen thì giữ nguyên).

• \(2\ K\ x_{1}\ x_{2}\ ...\ x_{K}\): Cho một tập hợp \(S\) gồm \(K\) đỉnh ngẫu nhiên. Hãy tính giá trị nhỏ nhất của biểu thức:

\[P(S) = \sum_{v \in S}^{}\text{dist}\left( v,\text{closest\_black}(v) \right) \cdot W\lbrack v\rbrack\]

Trong đó \(\text{closest\_black}(v)\) là đỉnh màu Đen có khoảng cách ngắn nhất tới \(v\) trên cây gốc (khoảng cách tính bằng số cạnh). Nếu tại thời điểm truy vấn, toàn bộ cây không có đỉnh nào màu Đen, hãy in ra -1.

Dữ liệu vào:

• Dòng đầu chứa số nguyên \(N\) (\(1 \leq N \leq 2 \cdot 10^{5}\)).

• Dòng thứ hai chứa \(N\) số nguyên \(W\lbrack 1\rbrack,W\lbrack 2\rbrack,\ldots,W\lbrack N\rbrack\) (\(1 \leq W\lbrack i\rbrack \leq 10^{6}\)).

• \(N - 1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u,v\) mô tả một cạnh của cây.

• Dòng tiếp theo chứa số nguyên \(Q\) (\(1 \leq Q \leq 2 \cdot 10^{5}\)).

• Tiếp theo là \(Q\) dòng (hoặc nhóm dòng) mô tả các truy vấn thuộc loại 1 hoặc loại 2.

Kết quả:

• Với mỗi truy vấn loại 2, in ra một số nguyên duy nhất là giá trị nhỏ nhất của \(P(S)\) tìm được, hoặc -1 nếu chưa có đỉnh Đen nào.

Ví dụ:

Ràng buộc:

• Subtask 1 (\(N,Q \leq 2000\)).

• Subtask 2 (\(N,Q \leq 2 \cdot 10^{5}\), không có truy vấn loại 1 - Đỉnh Đen cố định).

• Subtask 3 (\(\sum_{}^{}K \leq 2 \cdot 10^{5}\), đầy đủ các thao tác).