sPERbEETLE

摘要： CF161D Distance in Tree DP状态定义 根据子树位置\(+\)路径长度的统计设计状态。 \(Dp_{u,j}\)表示在以 \(u\) 为根的子树中，到 \(u\) 的距离恰好为 \(j\) 的节点个数。 初始化 \[dp_{u, 0}=1 \]状态转移方程式 在合并子树时来统计 阅读全文

摘要： 好用的树形DP定理 Kőnig 定理 二分图的最小点覆盖数 \(=\) 二分图的最大匹配数。 Gallai 恒等式 \[|最小点覆盖| + |最大独立集| = |V| \]树的直径\(\color{white}真的网址在这里！\) 定义 树上最长的不重复经过一个点的路径长度 ①二次dfs 解法 证明 阅读全文

摘要： 以下当前点为\(u\)，\(v\)为\(u\)的儿子 为什么树上可以用DP？ 每棵树代表着一个大问题，而其中的子树就是子问题。 统一思想 每个点/边/子树代表着一个问题的解，先把子树的解求出以求出包含该子树的子树的解。 对于以点为对象的DP 最大独立集 模版问题描述（仅类似） 在一棵树上有若干个点， 阅读全文

摘要： ε=(´ο｀*)))唉，还是考炸了，总该总结一下了。 关于树剖 树剖还是一如既往的垃圾，T4树剖细节没调出来，痛失35(还是25，忘了?)看来好记性不如在多打几遍，理解一下代码意思才是最重要的。 关于线段树 代码实现与思维能力不足，没有想出来具体合并方案。以后需要多多练思维，增强代码实现能力。 关于 阅读全文