好用的树形DP定理
Kőnig 定理
二分图的最小点覆盖数 \(=\) 二分图的最大匹配数。
Gallai 恒等式
\[|最小点覆盖| + |最大独立集| = |V|
\]
树的直径\(\color{white}真的网址在这里！\)
定义
树上最长的不重复经过一个点的路径长度
①二次dfs
解法
证明先不说，先说解法。
先随便找一个点，找到离这个点最远的点，再从这个最远点遍历找到最远点的最远点即可。
代码：
vector<int> g[N];
int maxn = 0, id = 0;void dfs(int u, int fa, int step) {if (maxn < step) maxn = step, id = u;for (auto v : g[u]) {if (v == fa) continue;dfs(v, u, step + 1);}
}
证明：
反证法，分情况：
-
- 当 \(u\) 在直径上，设直径是 \(s\) 到 \(t\)，离 \(u\) 最远的点是 \(v\)。
则 \(|uv|>|us|\) 那么两边都加上 \(|tu|\) 就是 \(|vt|>|ts|\) 不满足为直径。
-
当 \(u\) 在直径外，设直径是 \(s\) 到 \(t\)，离 \(u\) 最远的点是 \(v\)：
-
\(|uv|\) 与 \(|st|\) 有交点为 \(o\)，则就是上一种情况。
-
没有交点的话也是连通的，从连通那里连上也更长。
- 从这个端点往外找最远的一个点，一定是直径的另一个端点。
注意
此方法在有负边权时错误！
②树形DP
解法
这个证明就不说了
\(dp_1[u]\)：以 \(u\) 为根的子树中，从 \(u\) 出发向下的最长路径。
\(dp_2[u]\)：以 \(u\) 为根的子树中，从 \(u\) 出发向下的次长路径（且不与最长路径重合）。
如果 \(len > dp_1[u]\)，则\(dp_2[u] = dp_1[u], dp_1[u] = len\)
如果\(len > dp_2[u]\)，则\(dp_2[u] = len\)
最后在每次\(dfs\)的最后，取最大值，即：
\[ans = max(dp_1[u],dp_2[u])
\]
代码
自己想。
今日错误点
输出顺序反了，题目要求先输出叶子节点。