树形$dp$

OIergyy / 2024-11-21 / 原文

其实树形$dp$模板就是每次算出儿子结点的值，然后向父亲节点转移（但也有例外）。
模板
这个题每个状态除了结点还有选或不选的状态，这也是常用的
结点覆盖
这题本身就可以作为模型记。每个点有一个维度表示它被父亲/自己/儿子标记，在做转移。
最长距离
这题也是自成模型。有一个维度表示向下最大值，向下次大值，向上最大值，用向下最大值和向下次大值转移向上最大值。
树上背包（模板）
树上背包详解，讲的很详细，我就不讲了。
可以考虑加贡献
当一个东西会被使用多次，且我们正常做不好做，可以考虑加贡献。(例子)
树上最长链
求出每个结点向下最长路和次长路（保证不在同一儿子内），再合并。
这道题应用了最长链。这道题由于有很多链会被走两遍，当一个人走时，我们让最长路被走一遍，两个人时，我们让最长链被走一遍。
连通块个数(例子)$f[u]$表示以$u$为根连通块个数，有子树的$f[v]$相乘得到。
权值统计，又是一个自成模板的题。求所有路径权值积的和。树上求所有路径balabala~~可以想树上$dp$,$f[u]$代表$u$为路径两端点$LCA$的xx，此题可推得当考虑到$u$，它既是端点又是$LCA$,根据乘法分配律$f[u]=\sum (v向下的一条路径积*a[u])+a[u]=\sum (f[v]+1)*a[u]$,当$u$只时$LCA$时，贡献为$a[u]*\sum_{x}\sum_{y}路径x积*路径y积=a[u]*\sum_{x}路径x积\sum_{y}路径y积=a[u]*\sum_{v1\ne v2}f[v1]*f[v2]$
换根$dp$详解（例）