Tập độc lập cực đại trên cây

Buổi 65-66 — Mock HSG Dynamic Programming Trees
Points
50
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Cho một cây gồm $N$ đỉnh đánh số từ $1$ đến $N$. Mỗi đỉnh $i$ có trọng số nguyên dương $W_i$. Hãy chọn một tập các đỉnh sao cho không có hai đỉnh nào được chọn nối trực tiếp với nhau bởi một cạnh, và tổng trọng số các đỉnh được chọn là lớn nhất.

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 $W_1, W_2, \dots, W_N$.
  • $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ữ liệu ra

In ra tổng trọng số lớn nhất có thể.

Ví dụ
Input Output
5
10 20 15 5 30
1 2
1 3
2 4
2 5
50
1
100
100
Giới hạn

$1 \le N \le 10^5$, $1 \le W_i \le 10^9$.

Draft saved