UOJ Round #14
A. 最强跳蚤
30
$n \le 300$
$w \le 10^3$
每个质因子 $p$ 的次数必须是偶数。
从每个点开始 DFS，维护每个质因数的出现次数，预处理每个数的质因数分解即可。
时间复杂度 $\mathcal O(n^2 \log n)$，空间复杂度 $\mathcal O(w)$。
50
$n \le 3000$
把 $w$ 质因数分解，将出现过的质数离散化，可以发现至多出现 $\mathcal O(n \log n)$ 个不同的质数。
对离散化后的质数开桶维护出现的次数。
时间复杂度 $\mathcal O(n^2 \log n)$，空间复杂度 $\mathcal O(n \log n)$。
60
$n \le 100000$
$w \le 80$
$80$ 以内的质数不超过 $32$个，对第 $i$ 个质数分配一个权值 $2^{i - 1}$，一条边的权值就是 $w$ 所有质因子的权值的异或，一条路径的权值就是每条边权值的异或。
从根开始 DFS 求出根到每个节点的权值，那么 $u \rightarrow v$ 是可行的，当且仅当根到 $u$ 的权值等于根到 $v$ 的权值，把根到所有节点的权值排序统计一下即可。
时间复杂度 $\mathcal O(n \log n)$。
100
$n \le 100000$
对于每个质数分配一个 $[0, 2^{64})$ 内的随机数，于是一条合法路径权值一定是 $0$，而不合法路径只有 $\frac{1}{2^{64}}$ 是 $0$，这个概率可以忽略不计。
至于质因数分解，可以预处理 $10^4$ 以内的质数表，每次暴力分解。
时间复杂度 $\mathcal O(\sqrt w + n \pi(\sqrt w))$。
B. 人类补完计划
10
$n \le 11$
$m \le 20$
暴力枚举每条边是否在 $S_e$里，判断是否符合题目要求，把合法的案的权值计入答案。
时间复杂度 $\mathcal O (2^m m)$。
注意到不同的连通块之间的贡献独立，对每个连通块分别处理。
C. 思考熊
7
$n \le 1000$
$m \le 1000$
暴力枚举每个接应点，算出路径的权值和并更新答案，需要计算两点间的 LCA。
使用倍增或树剖做到 $\mathcal O(\log n)$ 询问，时间复杂度 $\mathcal O(n m \log n)$。
20
$n \le 10000$
$m \le 20000$
两个节点的 LCA 就是欧拉序中它们第一次出现的位置之间深度最小的节点。
使用用 ST 表做到 $\mathcal O(1)$ 询问，时间复杂度 $\mathcal O(n m)$。
40
$n \le 100000$
$m \le 100000$
如果只有插入操作，可以直接分块。
在插入的过程中每插满一块就对每个树节点预处理出到这个块中所有节点的距离的最大值，这是一个经典的树形 DP 的问题，可以在 $\mathcal O(n)$ 的时间内求出答案。
在询问的时候，对于完整的块可以直接得到答案，对于不完整的块，使用欧拉序和 ST 表单次 $\mathcal O(1)$ 计算权值。
时间复杂度和空间复杂度都是 $\mathcal O(n \sqrt n)$ 的。
那么现在问题来了，有删除的时候怎么办呢？有一种非常简单的方法就是不管。
60
$n \le 300000$
$m \le 300000$
保证没有第二类操作
如果点集 $S$ 给定，可以求出点集 $S$ 在树上的虚树，然后求出虚树上每一个点到它子树中关键点的最远距离 $d_i$ 和到子树外的关键点的最远距离 $u_i$ ，这个可以两遍 DFS 预处理。
现在要询问点 $x$ 到点集 $S$ 中的点的最远距离，先找到 $x$ 深度最大的祖先 $f$，使得 $f$ 在虚树的某一条边上，然后找到 $f$ 所在边的深度较深的端点 $v$，答案为 $\max(dis(x, v) + d_v, w_x - w_v + u_v)$，其中 $dis(x, v)$ 表示两点之间的距离，$w_v$ 表示 $v$ 到根路径上所有边的权值和。
那么如何找到 $f$ 呢，可以在虚树中找到 DFS 序小于等于 $x$ 的最后一个节点 $l$ 以及大于 $x$ 的第一个节点 $r$，可以通过一次二分解决，那么 $f$ 就是 $x$ 和 $l, r$ 的最近公共祖先中深度较深的那个。
在找到 $f$ 后二分出虚树中 DFS 序大于等于 $f$ 的第一个节点就是 $v$ 了。
至于修改，先来考虑插入，在只有插入的时候我们可以使用二进制分组来解决。
对最普通的二进制分组算法进行一点拓展来支持区间查询操作，在把两个块合并成一个新块的时候，保留原来两个块，并把新块作为原来两个块的父亲，这样我们就得到了一个线段树结构，这样在查询的时候，就可以和线段树一样，先找到完整组成询问区间的 $\mathcal O(\log n)$ 个块，然后分别在块中查询。
这样就把一个动态插入的问题转化成了静态的问题。
时间复杂度 $\mathcal O(n \log^2 n)$，空间复杂度 $O(n \log n)$。
80
$n \le 300000$
$m \le 300000$
$w_i = 0$
假设 $S$ 中距离最远的一对点是 $u$ 和 $v$，那么任意一个点 $x$ 到点集 $S$ 中的点的距离的最大值一定是 $x$ 到 $u$ 的距离或 $x$ 到 $v$ 的距离，所以就可以使用两个点来代替一个点集。
可以使用线段树，对线段树的每一个节点来维护这个区间中的点集的信息，合并两个点集信息时，可以把这两个最远点对一共四个点放到一起，那么它们两两之间距离最远的一对点就是合并后点集中距离最远的两个点。
询问答案时，对定位出的每个子区间计算答案并更新。
时间复杂度 $\mathcal O(n \log n)$。