UOJ Round #2
A. 猪猪侠再战括号序列
10
$n \le 4$
总长度为 $8$，整个序列一共有 $8!$ 种状态，枚举翻转的区间暴搜。
50
$n \le 100$
发扬人类直觉，最后的序列一定是左侧 $n$ 个 (，右侧 $n$ 个 )。
枚举左侧 $n$ 个位置，若出现 )，在右侧 $n$ 个位置随便找个 (，翻转并计入答案。
时间复杂度 $\mathcal O(n^2)$。
100
$n \le 10000$
复杂度瓶颈在于查找左括号位置及翻转序列。
使用平衡树维护括号序列以做到 $\mathcal O(n \log n)$。
谁写谁是大怨种。
发扬人类直觉，找到的 ( 要么是最前面的要么是最后面的。
- 如果是最后面的，翻转仍然是瓶颈。
- 如果是最前面的，则只需翻转端点。
每次枚举到一个左侧的 )，找到离它最近的 (，记其下标为 $l, r$，则一定有 $(l, r)$ 均为 )，翻转后仍为 )，因此仅翻转 $l, r$ 即可。
$r$ 随着 $l$ 的上升而上升，且始终有 $l_i = r_{i - 1}$，时间复杂度 $\mathcal O(n)$。
B. 跳蚤公路
10
$n \le 9$
$m \le 20$
如果存在负权环，那么一定存在简单负权环。
暴搜出所有简单环，对每个简单环求出 $x$ 系数之和 $k$ 以及 $w$ 之和 $b$，它不是负权环的条件 $kx + b \geq 0$。
对于每个结点找出所有 $1$ 能走到且能走到$v$ 的简单环，把这些条件收集起来就能求出整数解个数了。
注意 C++ 中 -10 / 3 = -3，是向零取整。
50
$n \le 40$
$m \le 1500$
简单环个数肯定不会少，所以我们要减少需要考虑的简单环数目。
对于每个简单环有 $k$ 和 $b$ 两个参数，若 $k$ 相同，则 $b$ 越小限制越紧，而 $b$ 就是忽略掉 $x$ 后的长度。
于是使用 Floyd，记 $f[v][u][k]$ 表示从 $v$ 出发到 $u$ 结束且 $x$ 前的系数为 $k$ 的最短路，$f[v][v][k]$ 即为包含 $v$ 的且 $x$ 前的系数为 $k$ 的最短环长。
时间复杂度 $\mathcal O(n^5)$。
注意 Floyd 的题一定要判 inf 及时 continue，否则会出现很多玄学错误。
60
$n \le 100$
$m \le 10000$
保证去掉所有的自环后图中不存在环
只处理自环就可以了，然后使用拓扑排序将限制下放。
时间复杂度 $\mathcal O(n + m)$。
C. 树上GCD
10
$n \le 2000$
枚举两个点 $(u, v)$，$\mathcal O(\log n)$ 时间计算 $LCA$ 及 $\gcd$ 并更新答案。
时间复杂度 $\mathcal O(n^2 \log n)$。
30
$n \leq 200000$
$p_i$ 在 $\{1, 2, \cdots, i - 1 \}$ 中均匀随机
随机生成的树的树高为 $\mathcal O(\log n)$。
枚举 $u$，计算以 $u$ 为 $LCA$ 的点对答案。
统计出 $u$ 子树种每个深度 $h$ 上的结点数量 $cnt[h]$。枚举深度 $h_1, h_2$，并将 $cnt[h_1] \cdot cnt[h_2]$ 累加到 $ans[\gcd(h_1, h_2)]$ 中。
统计答案的复杂度是 $\mathcal O(deg_u \cdot \log^2 n)$，$\sum deg_u = n$。
注意仅期望深度为 $\log n$，实际空间需要多开几倍。
每次统计答案时重新计算 $\gcd$ 会多一个 $\log$，需要预处理。
时间复杂度 $\mathcal O(n \log^2 n)$。
40
除根结点外的每个结点至多拥有一个孩子
把问题转化为，对于每个 $d$ 求出 $\gcd(h_1, h_2)$ 是 $d$ 的倍数的点对的数量，然后用一个 $\mathcal O(n \log n)$ 的莫比乌斯反演算出最终答案。
如果有 $f(d) = \sum_{d \vert n} g(n)$，那么有 $g(d) = \sum_{d \vert n} \mu(\frac{n}{d}) f(n)$。
从根结点挂下来若干条链，长度分别为 $h_1, \cdots, h_k$。
$u, v$ 在同一条链的情况可以方便计算。
$u, v$ 不在同一条链上时，LCA 即为根结点。
对于某个 $d$，第 $i$ 条链中高度为 $d$ 的倍数的点有 $\lfloor \frac{h_i}{d} \rfloor$ 个。
要统计 $k$ 条链中选出两条来的乘积总和，可以利用恒等式 $(x_1 + \cdots + x_k)^2 = x_1^2 + \cdots + x_k^2 + 2\sum_{1 \le i \lt j \le k} x_i x_j$ 求得。
由于 $d$ 与 $h_i$ 呈制约关系，时间复杂度 $\mathcal O(n)$。