UR#1
T1 缩进优化
枚举 $x$ 之后，枚举 $[ix,(i+1)x)$ 区间算贡献，复杂度是调和级数。
T2 外星人
首先 $a$ 从大到小排序，然后设 $f_i$ 表示当前值为 $i$ 的方案数，转移是枚举一个 $a_j\leq i$ 表示下一次有意义的取模，然后乘一个组合数啥的就行了。
T3 跳蚤国王下江南
直接把环拆成，最上面的点和下面的每一个点连边权是 $x^a+x^{len-a}$ 的边，然后树剖后分治 FFT 就是对的。
因为一个点只有一个重儿子，而只用 $i$ 和重儿子之间的边权会在分治 FFT 的时候有贡献，和轻儿子之间的连边是直接暴力统计上来的。而 $(i,son_i)$ 的边权最高次数和显然是 $\mathcal O(n)$ 的，所以复杂度还是对的。
UR#2
T3 树上GCD
显然要莫比乌斯反演。只需要统计 $g_k$ 表示 $k\vert f(i,j)$ 的对数再做莫反就行了。
对于一个 $k$，可以类似长剖 $\mathcal O(n)$ 的算出有多少 $g_k$。所以对于 $k\leq B$ 的所有值暴力求。
我的做法：对于 $k$ 较大的情况，发现一个点可能会成为 LCA 需要他有两个深度大于等于 $k$ 的儿子，而这样的点数不超过 $\frac n k$。所以这样暴力做狄利克雷后缀和再统计一下就能做到 $n+\frac n k\log\log n$ 求一个 $k$ 的答案。平衡一下大概就过了。
上面的东西有点唐。上面的东西换成长剖，不做狄利克雷后缀和，暴力求就对了。
UR#3
T3 链式反应
题意是，$f’(x)=\int a(x)f^2(x)+1$，求 $F$ 的前 $n$ 项系数。
考虑牛顿迭代。假设有 $f_0(x)$ 满足 $\displaystyle f_0’(x)\equiv g(f_0(x))\pmod {x^n}$，如何求出 $\bmod {x^{2n}}$ 意义下的一个解。
\[\begin{aligned} f_0'&\equiv g(f_0)\pmod {x^n}\\ f_1'&\equiv g(f_0)+g'(f_0)(f_1-f_0)\pmod {x^n}\\ f_1'-g'(f_0)f_1&\equiv g(f_0)-g'(f_0)f_0\pmod {x^n} \end{aligned}\]考虑把左边的形式变成 $(f_1h)’$。
\[\begin{aligned} (f_1h)'&=f_1'-g'(f_0)f_1\\ f_1'h+f_1h'&=f_1'-g'(f_0)f_1\\ \frac{h'}{h}&=-g'(f_0)\\ \end{aligned}\]设 $h=e^{r}$，则 $r’=-g’(f_0)$，可得：
\[h=e^{-\int g'(f_0)dx}\]所以两边同乘 $h$：
\[\begin{aligned} f_1'h-g'(f_0)f_1h&=(g(f_0)-g'(f_0)f_0)h\\ (f_1h)'&=(g(f_0)-g'(f_0)f_0)h\\ f_1&=\frac{\int (g(f_0)-g'(f_0)f_0)h}{h}\\ \end{aligned}\]直接牛顿迭代就行了。（真的跑得过全在线卷积吗）
UR#4
T2 元旦激光炮
经典题目，还是挺有意思的。以前觉得好难，现在还是能想出来的！
首先取 $l=\lfloor \frac k 3\rfloor$。比较 $a_l,b_l,c_l$。假设 $a_l>b_l,c_l$，则 $a[1,l]$ 一定全选，所以可以把 $k$ 的规模减少三分之一。不断做这个就行了。
T3 追击圣诞老人
一看就是 一类堆贪心前 k 优方案题。
堆里面元素的状态理应是一个三元组 $(i,j,v)$ 表示当前序列最后一个点是 $i$，当前权值总和是 $v$，并且序列的下一个数暂定为 $a_i,b_i,c_i$ 虚树上边权第 $j$ 大的点。这个可以用主席树做。
好像不能，空间刚刚好炸了。那咋办？？考虑再对于每个 $(a_i,b_i,c_i)$ 维护一个堆来支持查询第 $k$ 大。堆里面的元素是若干条链，权值是链上最小值。每次取出最小的链，删掉最小值后会断成两条链。现在问题变成了静态树链最小值。可以树剖，维护每个前缀的最小值，然后最后一段不完整的链用线段树查询。时间复杂度 $\mathcal O(n\log n)$，空间复杂度线性。
UR#5
T2 怎样更有力气
按照 $w$ 从小到大做。树剖，维护树上当前连通性的颜色段。每次暴力找到所有的颜色段，统计每种颜色的出现次数。
然后可以拿一个 map 之类的东西找到真的删掉的边，然后做补图 bfs。
T3 怎样跑得更快
典。
\[\sum_j f_j g_{(i,j)}x_j=h_i\]枚举 $d\vert(i,j)$，所以先求出 $g’$ 满足 $\displaystyle\sum_{d\vert n}g’(d)=g(n)$，这是一次莫反：
\[\sum_{d\vert i} \sum_{d\vert j} f_j g'_d x_j=h_i\]另 $v_i=\sum_{i\vert j}f_jx_j$，则上式为：
\[\sum_{d\vert i}g'_dv_d=h_i\]可以一次莫反解出 $g’_iv_i$。所以得知了 $v_i$。根据 $v_i$ 的定义可以再一次莫反解出 $f_ix_i$，这样就得知了 $x_i$。