树形$dp$

P6419 [COCI2014-2015#1] Kamp

换根$dp$，先以$1$为根，记$f_x$表示$x$的子树中的关键点到$x$的距离之和，$dis_{x, 1}$和$dis_{x, 0}$表示$x$的子树中关键点到$x$的最远和次远距离，注意不能在$x$的同一个儿子的子树中。

这样$1$节点的答案就是$f_1 - dis_{i, 1}$。

然后考虑换根，如果$x$的子树中没有关键点，那么它的代价是到父亲的边的权值加上父亲的最小代价，就相当于是先开车走到父亲处然后按照父亲的策略进行处理；否则先判断$x$的父亲往上走是否有关键点，没有就直接用$f_x - dis_{x, 1}$当答案；如果有关键点，那么进行换根求出目前$x$的子树中的最长路径，用$f_{fa}$减去即可。

P3177 [HAOI2015]树上染色

直接进行树上背包然后算将点染色的贡献即可，注意无论是刷表法还是填表法进行背包，首先先要保证$x$之前的子树中和$v$的子树中枚举的选择个数都是合法的，然后还要保证先合并转移再更新$siz_x$。

令$sum_x$表示$x$及$x$之前的子树总的大小，这时复杂度是$\sum (sum_v - siz_v) \times siz_v$，正好每两个节点之间被算了一次是$O(n ^ 2)$的，如果先更新$siz_x$的话复杂度会大一些，会$T$掉。

P1099 树网的核

在直径上进行尺取，每次对合法的一段计算它的轴心距即直径两端点到它的两端点的距离和它上面的节点到不在直径上的节点距离中最大的，然后从所有周新局中取$min$。

其实可以每次只计算直径两端点到它的距离取$min$最后再和直径上所有节点到直径外节点的最大距离取$max$，这样就是$O(n)$的了。

正确性证明如下，对于只计算直径两端点的贡献的得到的树网的核，直径上的点到直径外节点的路径有两种情况：第一种是经过树网的核，那么这时取$max$是对的，如果不经过的话，不可能比到直径两端点的距离大，如果比到直径两端点的距离大的话，可以重新构造更长的直径，和直径的定义不符，这种情况不成立。

P4516 [JSOI2018]潜入行动

$dp$状态和式子的转移都比较容易推出，但是在转移的时候用刷表***有重复计算的情况，答案会变大，所以要先将$dp$数组进行复制确保不会重复计算；如果是填表法，可以从大到小枚举放置的障碍的个数，但是当子树中枚举放置的障碍数为$0$时会出现自己的贡献多算的情况，把这部分单独拿出来处理就好了。

BZOJ1907 树的路径覆盖

考虑从叶子节点往上贪心进行计算，如果某个节点的儿子个数$ >= 2$那么就把其中两条路径在$x$处合并，从$x$的父亲往上重新开始一条新的路径，考虑如果不这么做，仍然会有一条路径往上延伸而路径条数不变，而合并之后的路径条数和往上延伸的条数是一样的，所以答案不会变的更劣。

HDU6035 Colorful Tree

正难则反的套路，正着不好计算，考虑计算没有颜色$x$的路径条数，也就是所有没有颜色$x$的连通块大小，这样就是颜色$x$的子树大小减去子树中下一次出现的颜色$x$的子树大小，注意最后还有整棵树最上面的一块，用整棵树的大小减去第一次出现的颜色$x$的子树大小。

状压$dp$

数据小的时候可以直接状压质因子，数据大的时候我们发现每个数大于$22$的质因子只有一个，那么就有一个经典套路。我们按照每个数字的最大质因子进行排序，对于质因子相同的区间分别处理，强行钦定其中一个人选择这个质因子，那么另外一个人为了不和他冲突就不能再在这些数里选了，可以进行转移。对于最大质因子小于$22$的，不会发生冲突，那么我们就把这段要处理的区间长度调整为$1$即可，即这个不存在的最大质因子不会对答案产生影响。

形式化的，我们先记录之前处理好的区间的$dp_{i, j}$表示两个人选择的方案数，然后每次对于要处理的区间，$f1_{i, j}$和$f2_{i, j}$分别表示强制第一个人和第二个人选择的方案数，那么$f1$和$f2$的转移可以用滚动数组进行优化：

\[f1_{i \cup s_{zhi}, j} += f1_{i, j} (s_{zhi} \cap j = 0) \]

\[f2_{i, j \cup s_{zhi}} += f2_{i, j} (s_{zhi} \cap i = 0) \]

这样最后对于合法的$dp_{i, j}$就等于$f1_{i, j} + f2_{i, j} - dp_{i, j}$，因为两个人选择的方案里面有重叠的部分。

CF453B Little Pony and Harmony Chest

因为$a_i$的值域很小只有$30$，然后我们发现$1$和任意数字都是互质的，所以$b$如果有一个大于$58$的数，我们将它替换成$1$会更优秀且一定满足条件，这样的话就限制了$b$的值域是从$1$到$58$，这中间有$16$个质数只需要状压质因子转移即可。

然后有一个小剪枝，对于每一个$a_i$，$b_i$都有确定的值域，假设$b_i$的值域最大是$x$，那么有

\[x - a_i = a_i - 1 \]

这样就有$x = 2 \times a_i - 1$。

P4294 [WC2008]游览计划

不难看出这是斯坦纳树的模型，不过在这道题里面，$dp$里面存的不是边权而是点权，这样的话在计算时的式子会有一点变化。

\[dis_{j, s} + f_i -> dis_{i, s} \]

\[dis_{i, sub} + dis_{i, s \oplus sub} - f_i -> dis_{i, s} \]

因为注意到通过传统的式子更新$dis_{i, s}$时$f_i$会重复计算两遍，所以要减去一个$f_i$。

本题难点在于如何输出方案，注意到每个$dis_{i, s}$的来源只有两种：从第一个式子转移过来也就是只连了一条边，这样可以在$dijkstra$的时候记录它的前驱，最后$dfs$的时候往前递归处理就行；从第二个式子转移过来只需要枚举$s$的子集观察是否有满足条件的$sub$和$s$，如果有的话分两部分递归即可。

Topcoder SRM 713 DFSCount

传送门

动态规划

树形\(dp\)