拖着疲惫打开新的一个月，也要加油啊。
1日
P4220 [WC2018]通道
边分治 + 虚树 + 树形 DP。
三棵树 \(T_1,T_2,T_3\)，最大化 \(dis_1(u,v)+dis_2(u,v)+dis_3(u,v)\)。
那么 \(T_1\) 先边分治，设每次重心边端点为 \(eu,ev\) 那么答案就是 \[ dis_1(eu,u)+dis_1(ev,v)+deep_2(u)+deep_2(v)-2deep_2(\operatorname{LCA}_2(u,v))+dis_3(u,v) \] 我们得到分治的连通块，将重心边两边的子树分别染成黑色和白色，然后在 \(T_2\) 对这些点建立虚树。在虚树上 dfs，那么 \(\operatorname{LCA}_2(u,v)\) 就固定了，只要统计属于不同子树且颜色不同的 \(u,v\) 的最大答案。
然后设 \(w(u)=dis_1(eu)+deep_2(u)\)，把 \(w(u),w(v)\) 加到 \(T_3\) 中 \(u,v\) 的路径长度上，最大化这个新的 \(dis_3'(u,v)\) 即可。
现在就是虚树上答案的统计问题了，合并两个 \(T_2\) 的子树其实就是合并 \(T_3\) 上的两个点集。这里有个结论：点集 \(A,B\) 最长路径的端点分别为 \(u_A,v_A,u_B,v_B\)，那么 \(A\cup B\) 的最长路径的端点一定是 \(\{u_A,v_A,u_B,v_B\}\) 中的两个。答案也同时类似的更新一下。
\(\operatorname{LCA}\) 使用 st 表 \(\mathcal O(1)\) 查询。总复杂度 \(\mathcal O(n\log^2 n)\)。
2日
P4565 [CTSC2018]暴力写挂
边分树合并。
化简题目，就是最大化 \(\frac{1}{2}(depth(x)+depth(y)+dis(x,y)-2depth'(\operatorname{LCA}'(x,y)))\)。如果类似 通道 一题用边分治和虚树来做是 \(\mathcal O(n\log^2n)\)，据说会被卡。
需要边分树合并。边分树类似 Kruskal 重构树，我们在边分治时，将前为根的边作为一个新点，该点的信息维护两边的子树信息合并的答案，也就是用边代表一个连通块。边分树可以通过边分治建立。因为边分树是二叉树，所以合并方法和线段树一样。
对每个点建立动态开点边分树，一开始就是一条链，链上每一个点就代表每次的边分治的根，记录对应答案。在第二棵树上 dfs，就固定 \(\operatorname{LCA}'(x,y)\)，统计属于不同子树的 \((x,y)\) 以最大化上式的值。合并的时候同时更新答案即可。
边分树的合并单次 \(\mathcal O(\log n)\)，总复杂度 \(\mathcal O(n\log n)\)。注意要特判 \(x=y\) 的情况。
CF757G Can Bash Save the Day?
可持久化边分树。
点分树 + 平衡树 的时间空间复杂度都是 \(\mathcal O(n\log^2n)\) 的过不去。观察到是区间询问，如果能让分治树可持久化就好了。而边分树是二叉树，是方便可持久化的。
边分树上维护到有效点到根的距离和和个数，类似主席树进行可持久化，询问差分一下。修改操作只有某一个版本的边分树有变化，直接改。
复杂度 \(\mathcal O(n\log n)\)，稍微卡了一下常，在 Luogu 和 Codeforces 都是 rank1。
P1742 最小圆覆盖
计算几何 + 随机增量法。
随机增量法：枚举 \(i\)，找到 \([1,i)\) 中不在圆内的点 \(j\)，由 \(i,j\) 更新圆；再找到 \([1,j)\) 中不在圆内的点，由 \(i,j,k\) 更新圆。可以 证明 复杂度为 \(\mathcal O(n)\)。
问题在于如何由三个点 \(A,B,C\) 确定外接圆，设三个向量 \(\vec a,\vec b,\vec c\)，我们要求 \(AB\) 和 \(BC\) 垂线交点。可以通过向量的加减、旋转得到垂线的一点 \(\vec p\) 和单位向量 \(\vec v\)。列方程 \((\vec{p_1}+t\vec{v_1}-\vec{p_2})\cdot \vec{v_2}=0\) 得到 \(\displaystyle t=\frac{(\vec{p_2}-\vec{p_1})\cdot \vec{v_2}}{\vec{v_1}\cdot\vec{v_2}}\)。
3日
P4886 快递员
点分治。
以重心为中心点，算出询问点对的距离的最大值，再分治按重心移动。把距离最大的若干个点对拎出来：
- 如果有一个点对分属不同子树，那么移动中心点答案只会不变或者更劣；
- 剩下的点对一定是两个点在同一棵子树的情况，如果这样的点对大于等于两个，移动中心点只会更劣；
- 唯一可以移动的情况是只有一个点对为最大值且两点在一个子树，那么递归进该子树。
复杂度 \(\mathcal O(n\log n)\)。
CF566C Logistical Questions
点分治。
先考虑一条链的情况，设 \(f(x)\) 表示 \(\sum_i dis(x,i)^{1.5}\)，我猜显然这是一个下凸的单峰函数，那么可以在链上二分，计算 \(x\) 和相邻点的 \(f\) 值，递归到更小的一侧。
放到树上，就是用点分治来代替二分。由于单峰函数的和还是单峰函数，所以树上最优的中心点只有一个。怎么判断中心点 \(u\) 到其它点 \(f\) 值变化的走向？求导。我们求出每个子树 \(v\) 的函数值和的导数 \(s(v)\)（也是导数和）。设 \(d_i\) 表示 \(i\) 到 \(u\) 的距离，\(\Delta d\) 表示 \((u,v)\) 边的长度，则 \(u\) 转移到 \(v\) 的 \(f\) 值为 \[ \sum_{i\not\in tree(v)}(d_i+\Delta d)^{1.5}-\sum_{i\in tree(v)}(d_i-\Delta d)^{1.5} \] 求导得 \[ \sum_{i\not\in tree(v)}1.5\sqrt{d_i+\Delta d}-\sum_{i\in tree(v)}1.5\sqrt{d_i-\Delta d} \] 找到一个 \(v\) 满足上式小于 \(0\) 就递归下去。复杂度 \(\mathcal O(n\log n)\)。
4日
P5395 第二类斯特林数·行
二项式反演 + NTT。
由组合意义（\(n\) 个物品放到 \(m\) 个盒子，枚举有 \(i\) 个盒子非空，划分 \(n\) 为 \(i\) 个集合，再乘上排列数）得 \[ m^n=\sum_{i=0}^m \begin{Bmatrix}n\\i\end{Bmatrix}i!\binom{m}{i} \] 二项式反演得 $$ \[\begin{aligned} \\ \begin{Bmatrix}n\\m\end{Bmatrix}&=\frac{1}{m!}\sum_{i=0}^m(-1)^{m-i}\binom{m}{i}i^n \\ &=\sum_{i=0}^m\frac{(-1)^{m-i}}{(m-i)!}\frac{i^n}{i!} \end{aligned}\]$$ 就可以 NTT 来 \(\mathcal O(m\log m)\) 计算卷积了。