2026.2.3
咕咕咕。
Distance in Tree
求树上距离为 \(k\) 的二元组个数。
性质：节点只搜它子树内的，也可以覆盖所有情况，不用往父亲搜。
因为向上搜会和父亲向下搜重复计算，所以并不用往上搜。
剩下的就很简单了，\(dp_{i,j}\) 表示第 \(i\) 个点的子树距离为 \(j\) 的有多少个。
Three Paths on a Tree
不会证。
可以充分考虑样例，发现答案为两个端点+一个任意点
接下来证明：
先转换答案：\(2f(x,y,z)=dist(x,y)+dist(y,z)+dist(x,z)\) 这个很好证，画一下图就能证明
反证法，如果第 \(x\) 个点的最大答案为 \(s',t'\)，则有 \(dist(s't')+dist(s'x)+dist(t'x)>dist(st)+dist(sx)+dist(tx)\)
很显然，\(dist(s't')<dist(s,t)\)。
同时 \(dist(s'x)+dist(t'x)=dist(s't')+2dist(lca(s',t'),x)<dist(st)+2dist(lca(s,t),x)\)，得证。
P1110 [ZJOI2007] 报表统计
wawawa 我太强了。
操作 2 很显然，通过记录插入位置的前一个和后一个来计算，后一个还不变，只用记录前驱。
然后计算贡献 \(val=min(abs(pre-x),abs(nex-x))\)，此时还需要减掉原来 \(pre\) 和 \(nex\) 的贡献。
开一个 set 维护也行，我“懒”就开的平衡树。
操作 3 更显然了，插入的数 \(x\) 只有第一个小于它和第一个大于它的会有贡献，在平衡树里找前驱后继就行。