Tập Độc Lập Trọng Số Lớn Nhất

Buổi 34 — Tree DP & Rerooting Dynamic Programming
Points
42
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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 dương $a_i$. Hãy chọn một tập con các đỉnh sao cho không có hai đỉnh nào kề nhau cùng được chọn 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 $a_1, a_2, \dots, a_N$.
  • $N - 1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$.
Dữ liệu ra
  • Một số nguyên duy nhất là tổng trọng số lớn nhất.
Ví dụ
Input Output
5
3 2 1 4 5
1 2
1 3
3 4
3 5
12
Giới hạn
  • $1 \le N \le 10^5$
  • $1 \le a_i \le 10^9$
Draft saved