Tập Độc Lập Trên Cây
Points
45
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ố $w_i$ (có thể âm hoặc dương).
Một tập hợp các đỉnh $S$ được gọi là tập độc lập nếu không có hai đỉnh nào trong $S$ được nối trực tiếp với nhau bởi một cạnh của cây.
Hãy tìm tổng trọng số lớn nhất của một tập độc lập (có thể chọn tập rỗng với tổng bằng $0$).
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên $N$ ($1 \le N \le 10^5$).
- Dòng thứ hai chứa $N$ số nguyên $w_1, w_2, \dots, w_N$ ($-10^9 \le w_i \le 10^9$).
- $N - 1$ dòng tiếp theo, mỗi dòng gồm hai số nguyên $u, v$ mô tả một cạnh của cây.
Dữ liệu ra
- Một số nguyên duy nhất là tổng trọng số lớn nhất của tập độc lập.
Ví dụ
| Input | Output |
|---|---|
| 5 4 10 3 2 5 1 2 1 3 2 4 2 5 |
13 |
Giới hạn
- $1 \le N \le 10^5$
- $-10^9 \le w_i \le 10^9$
Community Discussion