P3354 [IOI2005] Riv 河流
如果我们设 \(f_{u,j}\) 表示子树 \(u\) 内放了 \(j\) 个伐木场的答案，发现很难转移。
我们多加状态，设 \(f_{u,i,j}\) 表示子树 \(u\) 放了 \(j\) 个伐木场，木材全部运到 \(i\) 去最小代价。\(i\) 是 \(j\) 祖先。
继续设 \(g_{u,i,j}\) 表示 \(u\) 建了伐木场，子树 \(u\) 放了 \(j\) 个伐木场，木材运到 \(i\) 去最小代价。
这是个背包的模型，合并儿子的答案即可。
事实上，\(v\) 转移到 \(u\) 的时候是用不到 \(g\) 的，我们用 \(g\) 把 \(f\) 更新即可，
P3565/P5904 [POI2014] HOT-Hotels（加强版）
简单版的话，我们可以先枚举两个点 \(u,v\) 出来。得到这两个点路径的中点 \(mid\)。
设 \(u,v\) 到 \(mid\) 的距离为 \(d\)，那么我们要求的是到 \(mid\) 距离为 \(d\) 的点的个数（除去 \(u,v\)）。
事实上，我们只需要计算 \(mid\) 为根，求距离为 \(d\) 的点的个数算贡献即可。
困难版我们无法这么算。为了避免算重，钦定一个根。设 \(f_{u,i}\) 表示 \(u\) 子树内距离 \(u\) 为 \(i\) 的点数，
\(g_{u,i}\) 表示 \(u\) 子树内还要一个距离 \(u\) 为 \(i\) 的点就可以形成三元组的二元组个数。转移显然。
计算答案有两种，一种是三个点都在 \(u\) 子树内的，一种是 \(2\) 的点在 \(u\) 子树内，一个在外。
然而这样还是 \(O(n^2)\)。因为状态数与深度有关，考虑长链剖分。
长剖的过程是这样的：每次直接继承重儿子的信息，合并轻儿子暴力。
由于每个点只会在重链顶端暴力合并，所以时间复杂度为 \(O(n)\)。
再用指针分配内存，做到空间复杂度 \(O(n)\)。
P10408 「SMOI-R1」Apple
其中一个 subtask 的做法是操作分块，每次询问直接暴力计算块内修改的贡献，每个块结束重构一遍。
回到正解，我们从 OR-FWT 的过程出发。
我们如果每次修改，都做一遍完整的 fwt，每一次就得 \(O(n2^n)\)，然而查询 \(O(1)\)，启示我们去平衡。
所以我们每次单点修改，都从分治树底向上做 \(n/2\) 层。
然后我们每次查询的时候，查询的是 \(x\)，那么 \(x+k2^{n/2}\) 的点才能做贡献，继续分治上去即可。
已经完成平衡，每次操作复杂度是 \(\frac{n}{2}\cdot 2^{\frac{n}{2}}\)。