Ba Lô Phụ Thuộc Trên Cây

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