怎么都做过 uoj Round。/kk/kk/kk
只收录 UOJ 自己的题目，一些官方比赛题就算了。
没写题解不意味着没做，有的忘了写或者太草率了就算了。
部分前言删了。
【UER #1】DZY Loves Graph
题解
操作树一定形如一个毛毛虫。
考虑可撤销并查集维护联通块。
对于操作树上主干边暴力进行修改操作。
对于非主干边，可以只计算出答案。
加一条边可以使用并查集查询，删若干边的答案可以直接调之前某个版本的答案。
总复杂度 \(O(n+q\log n)\)。
【UR #1】缩进优化
题解
考虑枚举每个 \(x\) 计算答案。
假设值域为 \(v\)，我们只用知道若干区间内的总和及带权和即可。
使用前缀和即可维护。
总复杂度 \(O(n+v\log v)\)。
【UR #1】外星人
题解
先排序，然后考虑有效的数一定单调减，我们在这些位置决策。
假设 \(a_1\ge a_2\ge a_3\ge\dots\ge a_n\)。
假设 \(f_{i,v}\) 表示考虑到第 \(i\) 项，模后值为 \(v\) 的方案数。
特别的，\(f_{0,v}=[v=x]\)。
显然
\[f_{j,v\bmod a_j}\leftarrow\frac{(n-i-1)!}{(n-j)!}f_{i,v}\quad(i<j) \]于是直接前缀和优化 dp 就是 \(O(nv)\) 的了。
【UR #2】跳蚤公路
题解
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\) 应当满足
\[-\frac{f(s,b)}{b}\le x\le-\frac{f(s,a)}{a} \]考虑怎么快速计算出 \(f(s,j)\)。
考虑用 SPFA 松弛，如果计算过程中出现任一恒负环就无解。
否则 SPFA 可以在 \(O(n^3m)\) 内出解：分层图边数 \(O(nm)\)，点数 \(O(n^2)\)。不过我写了如果进队 \(8n\) 次就直接判无解，这样就是 \(O(n^2m)\) 的了。
垂死病中惊坐起，这个复杂度假的！
我们大力猜测出题人没卡，然后大力写就是了。
【UR #2】树上GCD
题解
我们考虑分开 \(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)\)。
【UR #3】铀仓库
题解
Fact 1：任意一种选法方案的最小时间是到起点距离和的 \(2\) 倍。
Fact 2：任意一种最优解均可以从某个已有的位置开始，向左右挑一个近的扩展，来得到。
我们枚举起点，然后二分套二分，即为 \(O(n\log n\log v)\)。
考虑怎么优化。
注意到当起点单调增时，我们总可以令最优的最右端点不减，尺取即可解决。对左右暴力扩展即可。
【UR #3】链式反应
题解
简单 GF。
假设答案的 EGF 为 \(g\)，光子选法的 EGF 为 \(f\)，则
\[g'=1+g^2f/2 \]写一个在线卷积即可解决。
即，设 \(h=g^2/2\)，则有
\[g'=1+hf,h=g^2/2 \]从而
\[g_n=[n=1]+\frac{1}{n}\sum_jh_jf_{n-j-1} \]\[h_n=\frac12\sum_jg_jg_{n-j} \]直接同时处理就好了。总复杂度 \(O(n\log^2n)\)。