Trồng rừng

Một vùng đồi có $n$ lô đất, đánh số từ $1$ đến $n$, nối với nhau bởi $n-1$ lối mòn sao cho từ mỗi lô có thể đi tới mọi lô khác (các lô và lối mòn tạo thành một cây). Nếu trồng rừng trên lô $i$, ban quản lý thu được giá trị $a_i$; giá trị này có thể âm (lô đất xấu, trồng sẽ lỗ). Để chống cháy lan, không được trồng rừng trên hai lô nối trực tiếp với nhau bởi một lối mòn.

Yêu cầu: Chọn một tập các lô để trồng rừng (có thể không chọn lô nào) sao cho tổng giá trị lớn nhất, và chỉ ra một cách chọn như vậy.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $n$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.
• Mỗi dòng trong $n-1$ dòng tiếp theo chứa hai số nguyên $u,v$: có lối mòn nối lô $u$ và lô $v$.

Dữ liệu ra

• Dòng thứ nhất in tổng giá trị lớn nhất.
• Dòng thứ hai in số $k$ là số lô được chọn.
• Dòng thứ ba in $k$ số hiệu lô được chọn, theo thứ tự bất kỳ (để trống nếu $k=0$).

Nếu có nhiều cách chọn đạt tổng lớn nhất, in một cách bất kỳ.

Ràng buộc

• $1\le n\le 2·{10}^5$.
• $-{10}^9\le a_i\le {10}^9$.
• $1\le u,v\le n$, các lối mòn tạo thành một cây.

Subtasks

• Subtask 1 ($30\%$ số điểm): $n\le 20$.
• Subtask 2 ($30\%$ số điểm): lối mòn thứ $i$ nối lô $i$ và lô $i+1$ (các lô xếp thành một hàng).
• Subtask 3 ($40\%$ số điểm): không có ràng buộc gì thêm.

Ví dụ