Gọi **dp[u][i][0 / 1]** là min_cost thăm **(i)** thằng con **(v)** trong cây con gốc **(u)** và **[0 / 1]** có nghĩa là không quay trở lại hoặc quay trở lại đỉnh **(u)** sau khi thăm xong nhánh **(v)**.\
Dễ thấy trường hợp cơ sở là:ㅤ **dp[u][1][0 / 1]** = 0 \
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ **dp[u][i][0 / 1]** = infinity (i > 1) \
**Nhận xét:** Với mọi đỉnh cha **(u)** bất kỳ chỉ xác đỉnh duy nhất 1 đỉnh con **(v)** mà từ đó **(u)** đi xuống **(v)** và từ **(v)** không quay trở lại **(u)** ㅤ\
Ví dụ với cây: \
1 - 2 \
1 - 3 \
Muốn thăm cả 3 đỉnh ta có thể đi: ㅤ1 → 2 → 1 → 3 \
Không tồn tại cách đi: ㅤ1 → 2 → 3
Công thức truy hồi có thể sẽ khó hiểu nên bạn phải vẽ cây ra để dễ hình dung hơn:
- Nếu không quay lại **(u)** có nghĩa là xác định duy nhất đường đi từ **(u)** xuống **(v)** và không quay lại. \
ㅤNhững thằng **(v')** được thăm trước đó phải quay trở lại **(u):** ㅤ**dp[u][i + j][0]** = min(ㅤ**dp[u][i][1]** + **dp[v][j][0]** + **w**ㅤ) \
ㅤNhững thằng **(v')** được thăm sau đó phải quay trở lại **(u):** ㅤ**dp[u][i + j][0]** = min(ㅤ**dp[u][i][0]** + **dp[v][j][1]** + **2 * w**ㅤ)
- Nếu quay trở lại **(u)** thì cũng phải quay trở lại **(v)**. \
ㅤ**dp[u][i + j][1]** = min(ㅤ**dp[u][i][1]** + **dp[v][j][1]** + **2 * w**ㅤ)
Đáp án sẽ là: **dp[1][i][0]** (1 ≤ i ≤ n) \
\
**Code:** O(n^2) (Áp dụng knapsack on tree).
https://ideone.com/dRdCvI
hungkm466
Created at
0 likes