猪猪侠再战括号序列

算法一

有一个超良心测试点满足 $n\le 4$。注意到 $8$ 个元素的排列最多 $8!$ 个，所以直接使用 bfs 或者 dfs 搜索，每次对于一个序列枚举所有可能的翻转区间然后搜下去就好了。可以获得 10 分。

算法二

算法一显然太无脑了。考虑翻转操作其实用起来非常不爽，因为牵连的元素个数太多。如果题目允许你每次交换序列中的两个元素的位置，那么其实要好办很多。

于是我们重新设定目标，把目标序列变为一个显然是合法的括号序列，类似这样 “(((())))”。

我们从左往右依次处理原序列的前 $n$ 个括号，如果发现有一个右括号，我们就在右边随便找个左括号。由于左括号和右括号都是 $n$ 个，所以我们总能找到。然后我们把当前位置到那个左括号之间的序列翻转过来，这样当前位置就很开心的成了左括号。翻转过来之后当然中间的括号一团糟啦！不过我们是从左往右考虑，所以我们只用保证当前位置以左是与目标一致的。至于右边嘛，这是以后的事情了。

暴力在右边找左括号，然后再暴力翻转序列就能做到 $O(n^2)$ 了。可以获得 50 分。

算法三

对于算法二，用 splay 维护括号序列找左括号以及翻转就能做到 $O(n\log n)$ 了，可以获得 100 分。不过貌似脑洞太大，没人会这么做。

算法四

好吧其实自己手玩下就清楚了。我们不要“随便找个左括号”，我们就找当前位置右边的第一个左括号。那么当前位置到那个左括号之前肯定都是右括号，翻转过来也就只有两端变了。

好那么怎么找第一个左括号呢？显然第一个左括号的位置只可能越来越靠右，所以在上一次找到的左括号的位置基础上继续往右走就行了。

时间复杂度 $O(n)$，可以通过所有测试点获得 100 分。

另外我题目中说的是 $n$ 的范围哟，不是 $2n$ 的范围哟。爆数组的同学恭喜了，我还是放了你们一马给了 80 分。

跳蚤公路

算法一

题目中说超过 ${10}^{100}$ 叫发财，说白了就是从 $1$ 走到 $v$ 能歪到某个负权环上去瞎逛。

对于第 1 个测试点数据范围非常小。一个比较容易发现的事实是如果存在负权环，那么一定存在简单负权环（即不经过重复的结点）。于是我们用最暴力的方法搜索出图中所有的简单环，对每个简单环求出 $x$ 系数之和 $k$ 以及 $w$ 之和 $b$，列出它不是负权环的条件 $kx+b\ge 0$。

然后我们对于每个结点找出所有 $1$ 能走到且能走到$v$ 的简单环，把这些条件收集起来就能求出整数解个数了。可以通过 1 号测试点获得 $10$ 分。

要请各位注意的是 C++ 中 -10 / 3 = -3，是向零取整。因为这个被坑的同学恭喜了。

算法二

什么？你说你写不清楚找简单环？没关系，如果你裹得清楚这个算法的其余的部分还是可以得分的！看 6 号测试点，所有的简单环都是自环。做掉这个测试点就能获得 $10$ 分了。如果与算法一结合能获得 $20$ 分。

算法三

到这里我们发现基本思路就是找简单环列不等式。但是简单环个数肯定不会少，所以我们要减少需要考虑的简单环数目。

如前所述，对于每个简单环有个 $k$ 有个 $b$。仔细思考发现，如果 $k$ 相同，肯定是 $b$ 小的那个限制更紧。而 $b$ 就是忽略掉 $x$ 后的长度。

于是我们可以使用 Floyd。我们在 Floyd 的基础上多加一维记录 $k$，用 $f[v][u][k]$ 表示从 $v$ 出发到 $u$ 结束且 $x$ 前的系数为 $k$ 的最短路。这里的最短路是忽略了 $x$ 的。显然我们可以在 $O(n^5)$ 的时间内求出这个数组。然后 $f[v][v][k]$ 就是包含 $v$ 的且 $x$ 前的系数为 $k$ 的最短环长。

后面的部分与算法一相同。可以通过前 5 个测试点获得 50 分。结合算法二能获得 60 分。

算法四

下面来说正解了，这题其实有多种算法。

首先我们刚才玩了那么大一圈最后陷入的 Floyd 的不归路导致无法继续优化。让我们来想想，如果 $x$ 已知，你应该怎么做？

我们考虑传统的Bellman的大概思想，就是 $f[t][v]$ 表示至多走 $t$ 步，从 $1$ 号点出发到 $v$ 的最短距离。显然最短路一定是简单路，所以 $f[n-1]$ 与 $f[n]$ 必定相等。但是如果有负环那么肯定不相等，所以利用这个性质就能检测负环。

好，但是这仅仅只是图中有负环而已，我们还得知道这个负环会牵连哪些结点。我们就找出 $f[n][v]<f[n-1][v]$ 的所有 $v$ 然后看 $v$ 能走到哪些结点，那么这些结点都在负环上，其它结点则不在。

利用这个想法我们可以很简单地拓展为 $f[t][v][k]$，在原有基础上记录 $x$ 前的系数。然后我们拿出 $f[n-1]$ 和 $f[n]$ 进行对比。解如下不等式：

$$min\{kx+f[n][v][k]\}\ge min\{jx+f[n-1][v][j]\}$$

把 $x$ 的范围解出来然后去更新自己能走到的结点的可行范围就好了。

时间复杂度 $O(n^4)$，可以通过所有测试点获得 100 分。

为了方便数学弱的小白我们多说几句，怎么解那个不等式呢？一定是对于所有的 $k$ 求下面这个范围的交集：

$$\begin{gathered} kx+f[n][v][k]\ge min \\ jx+f[n-1][v][j] \end{gathered}$$

对于每个固定的 $k$，一定是对于所有的 $j$ 求下面这个范围的并集：

$$kx+f[n][v][k]\ge jx+f[n-1][v][j]$$

于是现在只剩初中数学难度了。

其他算法

好吧我们来讲其他做法。其实仔细思考下 6 号测试点的深层含义，摆明了一副得DAG者得天下嘛。我们可以找到所有的强连通分量缩起来。要知道，只有强连通分量里有可能出现环，而且强连通分量里一旦出现负环，每个强连通分量内的点都可以走到负环再走回来。这意味着强连通分量内每个点的可行 $x$ 范围相同。于是我们可以把强连通分量分开进行考虑，求内部存在负环的范围，然后再考虑对其它强连通分量的影响。（什么你不会求强连通分量？ Floyd 一遍求出 $h[v][u]$ 表示 $v$ 是否能走到 $u$，那么 $h[v][u]$ 和 $h[u][v]$ 同时为真时 $v$ 和 $u$ 在同一个强连通分量，这样就 $O(n^3)$ 求强连通分量了，对于此题来说足矣。）

而判断一个强连通分量内负环的取值范围，我们只用建一个超级源点向所有点连权值为 $0$ 的边，然后跑 Bellman-Ford 对于每个结点 $v$ 和每个 $x$ 前的系数 $k$ 求出最短距离 $d$，然后不存在负环的条件就是对于每个 $v$ 都满足 $kx+d\ge 0$。轻松解开就可以了。

（可能有人会问为何要建一个超级源，用强连通分量中任意一个点不行么？当然不行。比如某个点走到负环上需要走 ${10}^9$ 的距离，但是负环的权值仅为 $-1$。于是就得很久很久之后才会让这个点到自己的最短距离比 $0$ 小。感觉这算法八九不离十了，所以给的大约 80 分。）

UPD：（上面这个算法是错的……T_T……大家还是写算法四吧，质量有保障）

当然了，由于一个环永远只是贡献一个一次不等式，所以 $x$ 的解集肯定是个连续的区间或者空集。如果是连续的区间那么我们可不可以二分呢？或许你会脑洞大开不停地随机 $x$ 直到随机到一个 $x$ 满足不存在负环，然后通过二分求出左右边界。其实这个算法还是能骗不少分的。

树上GCD

算法一

枚举两个点 $u,v$，用 $O(\log n)$ 时间计算 LCA 和 gcd，并更新答案。复杂度 $O(n^2\log n)$。

当然你也可以枚举 LCA，然后往子树方向进行 bfs，由于计算 gcd 是 $O(\log n)$的，所以复杂度还是 $O(n^2\log n)$。

可以获得 10 分。

算法二

随机生成的树的树高为 $O(\log n)$。

枚举 $u$，计算以 $u$ 为 LCA 的所有点对的答案。计算时对 $u$ 的子树 DFS，统计出每个深度 $h$ 上的结点数量 $cnt[h]$。枚举深度 $h_1,h_2$，并将 $cnt[h_1]\cdot cnt[h_2]$ 累加到 $ans[gcd(h_1,h_2)]$ 中。注意还需把同一个子树内的多余计算给减掉。这样，统计答案的复杂度是 $O(deg[u]\cdot {\log }^{2}n)$，总和是$O(n{\log }^{2}n)$。另外，每个点最多被DFS到 $O(\log n)$ 次，所以DFS的总复杂度是 $O(n\log n)$。

于是总复杂度 $O(n{\log }^{2}n)$。可以获得 30 分。

算法三

我们可以把问题转化为，对于每个 $d$，求出 $gcd(h_1,h_2)$ 是 $d$ 的倍数的点对的数量。然后用一个 $O(n\log n)$ 的容斥算出最终答案。

第4个数据点中，从根结点挂下来若干条链，长度分别为 $h_1,\cdots ,h_k$。$u,v$ 属于同一条链的情况可以方便计算；$u,v$ 不在同一条链上时，LCA即为根结点。对于某个 $d$，第 $i$ 条链中高度为 $d$ 的倍数的点有 $\lfloor h_i/d\rfloor$ 个；我们要统计 $k$ 条链中选出两条来的乘积总和，可以利用恒等式 $(x_1+\cdots +x_k{)}^2=x_1^2+\cdots +x_k^2+2\sum _{1\le i<j\le k}{x}_i{x}_j$ 求得。

复杂度 $O(n)$。可以获得 40 分。

算法四

考虑点分治，每次取出当前树的中心 $c$。考虑所有 $u\to LCA(u,v)\to v$ 的路径经过$c$的点对 $(u,v)$ 所产生的贡献，共有两种情况：

1. $u,v$ 均在 $c$ 的子树内，此时 LCA 即为 $c$。和算法三类似，只是第 $i$ 条链中高度为 $d$ 的倍数的点的数量需要在处理出 $cnt$ 数组后花 $h_i/d$ 的时间统计，所以复杂度是$O(n\log n)$。
2. $u$ 在 $c$ 的子树内，而 $v$ 不在。我们把当前树的根节点记为 $root$，$father[c]$ 到 $root$ 的路径为 $father[c]=a_1,a_2,\cdots ,a_{k-1},a_k=root$。记 $c$ 下面的子树高度为 $H$，$a_i$ 旁边伸出的子树（即不包含 $a_{i-1}$ 的)的高度为 $h_i$。枚举 $a_i=LCA(u,v)$，那么 $v$ 位于 $a_i$ 旁边的子树中，然后我们仍然枚举 $d$，用 $h_i/d$ 的时间求出 $a_i$ 子树中高度为 $d$ 的倍数的结点数量；但我们还需要知道 $c$ 的子树中有多少点相对于 $a_i$ 的高度是 $d$ 的倍数，也就是说我们要在 $c$ 子树的 $cnt$ 数组中查询下标间隔为 $d$ 的子序列中的元素之和。注意到间隔为 $d$ 时，至多只有 $d$ 种这样的子序列，我们对重复查询进行记忆化。于是对于 $d<\sqrt{H}$，查询的复杂度不超过 $d\cdot H/d=H$，总共是 $\sqrt{H}\cdot H$；对于 $d>\sqrt{H}$，单次查询的复杂度为 $H/d<\sqrt{H}$。

所以一层分治的复杂度是 $O(n\sqrt{n})$的。根据主定理，总复杂度就是$O(n\sqrt{n})$。看起来有点卡常数？不，其实常数很小的。可以通过所有测试点获得 100 分。

见：http://uoj.ac/submission/2785

第二步如果使用比较暴力的方法还是可以通过 5 号测试点的。

其他算法

其实这题也可以用启发式合并做。我们还是可以用容斥转化为求 $d$ 的倍数的个数。如果 $v$ 和 $u$ 之间某个是另一个的祖先，那么显然可以 $O(n)$ 求出贡献到答案里。其它情况，对于 $d\le \sqrt{n}$，我们可以用dp解决。$f[v][d]$ 表示以 $v$ 为根的子树中深度为 $d$ 的倍数的有多少个，然后在递推过程中更新答案。

对于 $d>\sqrt{n}$，我们每次对于每个点求出数组 $f[v][d]$，表示 $v$ 为根的子树中深度为 $d$ 的结点有多少个。通过启发式合并求这个数组。合并过程中，如果两个子树中最深深度都大于 $\sqrt{n}$，那么才有可能出现同为 $d$ 的倍数的情况。此时暴力对于每个 $d$ 以间距 $d$ 查询并更新答案。由于两个数组长度都大于 $\sqrt{n}$ 这种合并只会出现至多 $\sqrt{n}$ 次，所以总时间复杂度就是 $O(n\sqrt{n}\log n)$。虽然看上去比算法四更卡常数但是其实没有什么办法让它达到上界，于是也可以通过所有测试点获得 100 分了。

见：http://uoj.ac/submission/2786