题目链接

给定一个$n$个点$m$条边的有向带权图，设起点到终点的最短路为$d$，求起点到终点满足权值总和小于等于$(d+k)$的路径数量

$1 \le p\le 10^9 $ , $1 \le n\le 10^5$ , $1 \le m\le 2 \times 10^5$ , $1 \le k\le 50$

感谢@oy 的贡献

题目链接

读入$n$个整数，选取其中若干个数，最多连续取$k$个，求取到数字和的最大值

$1\le k \le n \le 100000$

感谢@oy 的贡献

这是一个并不简单的背包类树形dp……

很自然地想到状态定义：$f[u][k][0/1][0/1]$表示以$u$为根的子树中，总共选择$k$个结点，其中除了$u$以外的所有结点均被监听到，$u$结点选或不选，$u$结点是否被覆盖的情况下，一共有多少种方案。

状态转移看似十分麻烦。每个结点$u$都有许多子结点，很难统计出每个子结点的所有情况（似乎在组合数学的范畴）。但是我们可以用十分巧妙的树形背包来进行状态转移。树上背包的转移套路是：

$$
f[u][i+j]=combine(f[u][i],f[v][j])
$$

相当于每递归访问完一个子结点，就把子节点上的状态与当前已经处理的状态一一配对，保证不重不漏且兼顾效率。具体的转移方程为：

$$
f[u][i+j][0][0]=\sum f[u][i][0][0]*f[v][j][0][1]
$$

$$
f[u][i+j][1][0]=\sum f[u][i][1][0]*(f[v][j][0][0]+f[v][j][0][1])
$$

$$
f[u][i+j][0][1]=\sum (f[u][i][0][1]*(f[v][j][0][1]+f[v][j][1][1])+f[u][i][0][0]*f[v][j][1][1]
$$

$$
f[u][i+j][1][1]=\sum (f[u][i][1][0]*(f[v][j][1][0]+f[v][j][1][1])+f[u][i][1][1]*(f[v][j][0][0]+f[v][j][0][1]+f[v][j][1][0]+f[v][j][1][1]))
$$

具体实现时还应注意：因为阶段（即扫描子结点个数）的划分，在每次转移前都要先记录原始的$u$结点上的数据，否则会导致混乱。

写的不好！计划重写一篇。

树形背包博大精深！

绝对不咕！