\(2024.1.1-2024.1.7\)

\(\color{royalblue}{P5903}\)

树上 \(k\) 级祖先模板，长链剖分。

\(\color{blueviolet}{CF1009F}\)

长链剖分优化 DP 板子，每次继承重子节点信息，指针处理下下标平移，剩余节点暴力合并，复杂度线性。

\(\color{blueviolet}{P5904}\)

长链剖分优化 DP。

设 \(f_{i, j}\) 表示节点 \(i\) 字数内距 \(i\) 距离为 \(j\) 的点的个数。

设 \(g_{i, j}\) 表示满足一下条件的无序点对 \((x, y)\) 个数，$i# 子树外若存在距 \(i\) 距离为 \(j\) 的节点 \(z\)，则 \((x, y, z)\) 是一组合法三元组。

边转移边统计答案，简单乘法原理处理即可。

\(\color{blueviolet}{P3441}\)

长链剖分优化贪心。

显著的，直径肯定要选，然后每次选的时候肯定跨直径最优，如果存在两对不跨直径的点对，显然可以转换为两个跨直径的点对。

把直径一端拎起来当根节点，然后取最长的 \(2m - 1\) 个长链即可。（因为发现上文说的那个东西和取叶子节点覆盖是等价的。）