笔记 2023.12.14：树上问题
[Ynoi2004] rpmtdq
支配对：\(i_1\leq i_2\leq j_2\leq j_1, dist(i_1, j_1)\geq dist(i_2, j_2)\) 时，称 \((i_1, j_1)\) 被 \((i_2, j_2)\) 支配，前者就无用了，选到区间只要包含 \((i_1, j_1)\) 就一定包含 \((i_2, j_2)\)。
点分治到 \(rt\) 时，记 \(d_x=dist(x, rt)\)，则支配对 \((i, j)\) 必须满足：
- \(i<j\land d_i\leq d_j\)，取 \(i\) 最大的。
- \(i>j\land d_i\leq d_j\)，取 \(i\) 最小的。
如果存在一个 \(k<i<j,d_k\leq d_j, d_i\leq d_j\)，你冷静一下发现 \((k, j)\) 被 \((k, i)\) 支配了，\(j\) 不用管它。
单调栈随便做做，搞出 \(O(n\log n)\) 个点对，最后 cdq 二位数点总是能做的。\(O(n\log ^2 n + q \log n)\)。
CF1019E Raining season
边分治完了以后把 \((\sum a_i, \sum b_i)\) 看作点，两边建凸包，合并凸包（疑似是 Minkowski 和），更新答案，疑似 \(O(n\log ^2n)\)，不知道外面有没有一棵大凸包要合并。
[NEERC2015] Distance on Triangulation
将 \(n-3\) 条对角线拿出来分治（使得分成的两个多边形点数尽量相等），对于分治的边，从分治的边开始 bfs，获取所有跨过这条边的询问的答案。向下递归时，将多边形劈成两个多边形。类似于一个神秘的猫树分治。
树
二分答案完了以后点分树一眼 \(O(n\log ^ 3n)\)。
CF757G Can Bash Save the Day?
因为你已经会了如何用点分树查询全局答案，所以用主席树维护前缀的答案。swap 操作只改一棵主席树。\(O(n\log^2 n)\)。
或者将 \(1\to p_i\) +1，查询 \(1\to x\) 的和也可以求那玩意。\(O(n\log^2 n)\)。
据说有 1log 高论。
[CTSC2018] 暴力写挂
边分治分成两个点集 \(A, B\)，不妨 \(A\) 靠近根，那么 \(A\) 中点 \(x\) 和任意 \(y\in B\) 的 LCA 确定。于是 \(dep_x-dep_{lca(x, y)}\) 确定。
考虑 \(dep'_y-dep'_{lca'(x, y)}\)。对涉及的点在 \(T'\) 上建虚树。将 \(dep_y\) 看作黑盒，在 \(T'\) 的虚树上，第一次 dp 将答案放在 LCA 上，第二次 dp 将 LCA 的信息放回 \(x\)，都是轻易的。
于是 \(O(n\log n)\)。注意建虚树可以需要归并一下。
[WC2018] 通道
边分治第一棵树，在第二棵树上建虚树，枚举第二棵树上的 LCA \(k\)，现在的答案形如：
\[d_1[x]+d_1[y]+w_{edge}+dep_2[x]+dep_2[y]-2dep_2[k]+dist_3(x, y) \]要求 \(x, y\) 在边分治上不同集合，\(LCA(x, y)=k\)。
将 \(x, y, 1\) 分别独立一下，变成什么 \(dist_3(x, y)+val_x+val_y+C\)，观察到这其实是一个直径的形式，你总可以将 \(val_x, val_y\) 挂在第三棵树的这些点上，所以这就是直径。
在第二棵树的子树上合并第三棵树的直径端点。
*[JOISC2020] 首都城市
对颜色 \(i\) 建虚树，虚树边上的其他颜色 \(j\)，连边 \(i\to j\)。
欲将选到 \(i\)，首先需要改所有 \(j\) 为 \(i\)，改完以后原来 \(j\) 的点也需要形成连通块，除非是被 \(i\) 隔开就不用管。
所以是最小的强连通分量。后面怎么做都行。怎么做啊？
sub
这个 ddp 太平凡了。
*LOJ6289 花朵
分治 ntt，其实不会很会具体做法。
ICPC2017 西安 D Islands
别学分治 ntt 了
[POI2014] HOT-Hotel
skipped
Another Boring Problem
树上莫队，求出树的 dfs 时的括号序列，在到达点、退出点时将其加入到序列。设每个点有两个出现位置 \(s_x ,t_x\)，则查询区间相当于 \([t_x ,s_y ]\) 加上可能存在的 LCA 的贡献（不是祖先就要加）。注意这里不是严格的括号序，反正就是遇到就把状态取反。最后的 kth 怎么分块都行。
*2021 集训队互测 Lovely Dogs
待补一下，反正后面是 dsu on tree 套路，前面数学很好玩。
CF888G 最小异或生成树
他是在 Trie 树上考虑的，考虑 boruvka 的时候你是从 \(1, 2, 4, 8, 16, \cdots\) 的 highbit 一位一位考虑的，所以你直接在 Trie 树上，你声称 Trie 树上一棵子树是 boruvka 过程中的一个连通块，在点 \(p\) 合并它的左右子树的连通块。启发式查询一下就能保证复杂度为 \(O(n\log ^ 2n)\)。
Rectangle
扫描线直接扫 \(O(\log n)\) 次就行。
*CF632F Magic Matrix
令 \(b_{ij}=\min_k\max(a_{ik}, a_{jk})\leq a_{ij}\)（取 \(k=i\)），那么有 \(a_{ij}\leq b_{ij}\leq a_{ij}\implies b_{ij}=a_{ij}\)。
然后不知道为什么它就是 \(i, j\) 的所有路径的边权最大值的最小值。
然后跑 Kruskal 暴力判定一下。
*LOJ574 黄金矿工
将这个诈骗的边权和去掉。考虑无修改，是模拟费用流，
*JOISC 2020 Day3 收获
这个人收完苹果之后，下一个是谁收苹果是固定的，建内向基环树，以后的事情就是一坨了。
标签：14,dep,2023.12,分治,笔记,leq,ij,树上,log From： https://www.cnblogs.com/caijianhong/p/17900938.html