Tập Độc Lập Trên Cây
Points
14
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho một cây gồm $N$ đỉnh đánh số từ $1$ đến $N$. Mỗi đỉnh $i$ có một trọng số nguyên $w_i$ (có thể âm, dương hoặc bằng $0$). Hãy chọn một tập hợp các đỉnh (có thể rỗng) sao cho không có hai đỉnh nào kề nhau cùng được chọn và tổng trọng số của 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 một số nguyên duy nhất là tổng trọng số lớn nhất tìm được.
Ví dụ
| Input | Output |
|---|---|
4\n10 20 30 40\n1 2\n1 3\n3 4 |
60 |
1\n-5 |
0 |
Giới hạn
- $1 \le N \le 10^5$
- $-10^9 \le w_i \le 10^9$
Community Discussion