C
题意：给定一棵树，定义简单路径 \(x \to y\) 是好的当且仅当 \(x\) 是路径中编号最小值，\(y\) 是路径中编号最大值。\(n\le 10^6\)。
赛时双 log 做法：点分治，设路径端点 \(x\) 到分治之间的最小值为 \(\min\)，最大值为 \(\max\)。
如果 \(x = \min\)，A 中加入二元组 \((x, \max)\)；\(x = \max\)，B 中加入二元组 \((\min, x)\)；其他情况不可能对答案产生贡献。
\((y, \max)\) 能和 \((\min, x)\) 拼成好的路径当且仅当满足 \(\max \le x\land \min \ge y\)，离线二维数点。
正解：类似点分树的建立方式，建立一颗 "max重构树"，具体来说，每次找到剩余树中最大的节点作为根，然后往下递归。
重要性质：所有满足 \(\max(y \to x)= x\) 的 \(y\) 都在 \(x\) 的子树中。
考虑 \(x\) 的父亲 \(fa\) 作为分治中心时的情况：
- 满足条件的路径一定不经过 \(fa\)，即 \(y\) 不能是重构树上 \(fa\) 其他子树中的节点。
- 不能经过比 \(fa\) 还大的节点，即 \(y\) 不能是重构树上 \(fa\) 到根的链。
- 剩下有可能合法的答案都在 \(x\) 子树中，考虑充分性。\(y\) 不能经过 \(fa\)，而 \(x\) 又是他子树中的最大值，显然有 \(\max(y \to x) = x\)。
同理建立 "min重构树"，\((x, y)\) 能产生贡献当且仅当一棵树上 \(x\) 是 \(y\) 的祖先，另一棵上 \(x\) 属于 \(y\) 的子树。
预处理树 1 的 dfs 序。遍历树 2，每到一个节点就将其树状数组的权值改为 1，查询 \((in_x, out_x]\) 中有多少点权值为 1。
如何快速建树？从小到大枚举点 \(i\)，将出边 \(j < i\) 所在连通块中最大点的父亲设为 \(i\)。时间复杂度 \(O(n\log n)\)。submission
加强版：CF1797F，支持动态挂叶子。
设max重构树为 T1，min重构树 为 T2。假设现在加入一个叶子 \(n + 1\)，连向 \(v\)。
根据定义，显然 \(n + 1\) 只有唯一的方式加入两棵树：\(n\) 连向 \(n + 1\)，作为 T1 的新根；\(n + 1\) 连向 \(v\)，作为 T2 的叶子。
对答案的影响是什么呢？由于修改过后所有点都是 T1 中 \(n + 1\) 的子树节点，因此只要计算 T2 中有几个祖先即可。submission
标签：重构,min,19,max,路径,CSP2024,fa,节点 From： https://www.cnblogs.com/Luxinze/p/18412904