题解: Poborcy podatkowi

Wzhone · 2024-10-29 14:51:45 · 题解

双倍经验

题意简述:

给定一棵 n 个点的树，你可以选择若干条长度恰好为 4 的不交链，可以不选。

方案的收益定义为选出的链的并集的边权和，求最大收益。

思路

首先一种显然的思路是dp, 我们非常自然的可以设f_{i, 0/1/2/3}表示到i点的时候上传一个0/1/2/3长度的最大收益.

我们考虑怎么转移.

转移的时候, 我们钦定一个点作为我们上传的边的来源(f_0不需要), 从这个点的f_0/1/2转移. 但是这个时候我们还有许多个子树没有决定. 我们分类讨论, 考虑在这一层使用背包的思想.

如果这个子树想要上传一个长度为3的链, 那么我们直接统计进入答案. 如果这个子树想要上传一个长度为2的链, 那么我们考虑让它和一个长度为0的链合并. 长度为0的链同理. 如果这个子树想要上传一个长度为1的链, 那么它还需要和一个长度为1的链合并.

那么对于每一个父节点, 我们可以设出式子