UOJ随做

操作树一定形如一个毛毛虫。

考虑可撤销并查集维护联通块。

对于操作树上主干边暴力进行修改操作。

对于非主干边，可以只计算出答案。

加一条边可以使用并查集查询，删若干边的答案可以直接调之前某个版本的答案。

总复杂度 \(O(n+q\log n)\)。

考虑枚举每个 \(x\) 计算答案。

假设值域为 \(v\)，我们只用知道若干区间内的总和及带权和即可。

使用前缀和即可维护。

总复杂度 \(O(n+v\log v)\)。

先排序，然后考虑有效的数一定单调减，我们在这些位置决策。

假设 \(a_1\ge a_2\ge a_3\ge\dots\ge a_n\)。

假设 \(f_{i,v}\) 表示考虑到第 \(i\) 项，模后值为 \(v\) 的方案数。

特别的，\(f_{0,v}=[v=x]\)。

显然

于是直接前缀和优化 dp 就是 \(O(nv)\) 的了。

upd：这个做法假了。

注意到发财等价于路径上存在负权环。

只用计算每个源点可能到达的点往自己在 \(x\) 在什么范围时可能有负权环，最后把其所能到达的点更新一下即可。

我们可以把每个 SCC 拆开来考虑。对每个 SCC 设其中一个点 \(s\) 作为源点即可，容易发现此时不存在负环等价于不存在经过 \(s\) 的负环。

设 \(f(p,j)\) 为从 \(s\) 点到 \(p\) 点经过 \(j\) 个 \(x\) 的情况下剩余部分的最小代价。

如果 \(f(s,0)=-\infty\)，显然始终存在负环。

否则如果 \(f(s,0)=0\)，假设 \(f(s,a)\) 与 \(f(s,b)\) 两项将导致 \(\mathbb R\) 上 \(x\) 解集为空（\(a<0<b\)），则有 \(\min\{f(s,a)+ax,f(s,b)+bx\}<0,\forall x\in\mathbb R\)，也即 \(\frac{f(s,b)}{b}<\frac{f(s,a)}{a}\)，从而 \(bf(s,a)+(-a)f(s,b)<0\)，于是 \(f(s,0)=-\infty\)，矛盾。

因此 \(\mathbb R\) 上必定存在一组合法的 \(x\)。容易发现，此时 \(x\) 应当满足

考虑怎么快速计算出 \(f(s,j)\)。

考虑用 SPFA 松弛，如果计算过程中出现任一恒负环就无解。

否则 SPFA 可以在 \(O(n^3m)\) 内出解：分层图边数 \(O(nm)\)，点数 \(O(n^2)\)。不过我写了如果进队 \(8n\) 次就直接判无解，这样就是 \(O(n^2m)\) 的了。

垂死病中惊坐起，这个复杂度假的！

我们大力猜测出题人没卡，然后大力写就是了。

我们考虑分开 \(u\) 是 \(v\) 的祖先的贡献，和不是祖先的贡献。

对于 \(u\) 是 \(v\) 祖先的部分，我们可以在 \(v\) 处统计合法的 \(\operatorname{dist}(u,v)\)，显然是 \(1\sim\operatorname{dep}(v)\)，差分即可得到每种方法的数目。（认为根节点深度为 \(0\)）

对于 \(u\) 不是 \(v\) 祖先的部分，我们考虑容斥。

考虑对每个 \(g\) 计算有多少点对 \(u,v\) 满足 \(g|\operatorname{dist}(u,r),g|\operatorname{dist}(v,r)\)，其中 \(r=\operatorname{lca}(u,v)\neq u,u<v\)。

考虑对 \(g>B\) 和 \(g\le B\) 讨论。

对于 \(g>B\) 的部分，我们考虑长剖，在 \(r\) 处统计 \(g\) 的贡献。

在合并一个短段时，暴力加上长段中其对应的贡献。

容易发现只在短段长度 \(>B\) 时才会统计，因此最多统计 \(n/B\) 次，枚举的 \(g\) 的总数目不超过 \(n\)，于是总复杂度即为 \(O(n^2/B)\)。

对于 \(g\le B\) 的部分，我们考虑对每个 \(g\) 暴力枚举答案，则我们可以对元素按模 \(g\) 余数的高度分类，进行 dp 即可。直接做单轮是可以做到 \(O(n)\) 的，故该部分总复杂度 \(O(nB)\)。

容斥的部分复杂度可以忽略不计，取 \(B=\sqrt n\)，总复杂度 \(O(n\sqrt n)\)。

实测 \(B\) 比较小的时候这个比较快。

考虑如何卡满这个复杂度。

考虑一条长度为 \(n/2\) 的链，并且在根节点处挂 \(n/4B\) 个长为 \(2B\) 的链。那么容易发现每次合并的复杂度是 \(O(n)\) 的。

这样就卡满了 \(O(n^2/B)\)。

Fact 1：任意一种选法方案的最小时间是到起点距离和的 \(2\) 倍。

Fact 2：任意一种最优解均可以从某个已有的位置开始，向左右挑一个近的扩展，来得到。

我们枚举起点，然后二分套二分，即为 \(O(n\log n\log v)\)。

考虑怎么优化。

注意到当起点单调增时，我们总可以令最优的最右端点不减，尺取即可解决。对左右暴力扩展即可。

简单 GF。

假设答案的 EGF 为 \(g\)，光子选法的 EGF 为 \(f\)，则

写一个在线卷积即可解决。

即，设 \(h=g^2/2\)，则有

从而

直接同时处理就好了。总复杂度 \(O(n\log^2n)\)。