Tập Độc Lập Trên Cây

Buổi 34 — Tree DP & Rerooting Buổi 40 — Contest Chặng 5
Points
14
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ó 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$
Draft saved