Ba Lô Phụ Thuộc Trên Cây
Points
62
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 có gốc tại đỉnh $1$, và một chiếc ba lô có sức chứa tối đa $W$. Mỗi đỉnh $i$ có trọng lượng $w_i$ và giá trị $v_i$. Bạn muốn chọn một tập hợp các đỉnh sao cho tổng trọng lượng không vượt quá $W$ và tổng giá trị là lớn nhất, với điều kiện: một đỉnh $u \ne 1$ chỉ có thể được chọn nếu đỉnh cha của nó cũng được chọn.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N$ và $W$.
- Dòng thứ hai chứa $N$ số nguyên $w_1, w_2, \dots, w_N$.
- Dòng thứ ba chứa $N$ số nguyên $v_1, v_2, \dots, v_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 giá trị lớn nhất có thể đạt được.
Ví dụ
| Input | Output |
|---|---|
4 5\n2 2 3 1\n10 20 25 15\n1 2\n1 3\n2 4 |
45 |
Giới hạn
- $1 \le N, W \le 500$
- $1 \le w_i \le 500$
- $1 \le v_i \le 10^6$
Community Discussion