十月了。
我知道我的做法很唐，不要攻击我?
首先考虑 \(s=2\) 的部分分：当 \(s\) 固定的时候我们直接算出每个点被经过的期望次数，然后把 \(u\rightarrow v\) 路径上的期望 \(E\) 加起来即可。
对于期望次数：有式子 \(E(u) = \sum_{(u,v)\in e\land v\neq 1}p(v\rightarrow u)\times E(v)+[u=s]\)，其中 \(p(v\rightarrow u)\) 是 \(v\) 一步走到 \(u\) 的概率。这是一个高斯消元的形式，可以用树上高消在 \(O(n\log)\) 的时间内完成。这样我们解决了 \(s\) 固定的情况。
考虑 \(s\) 不定的情况：我们把询问离线然后尝试换根。这里首先需要知道树上高消的本质：我们把每个点（除了根）的 \(E(u)\) 表示成了关于 \(E(fa_u)\) 的（严格）一次多项式，然后 \(E(s)\) 可以直接求得；最后从顶至底回代。
我们设 \(x=E(s)\)，则 \(s\) 的一个儿子 \(v\) 的 \(E(v)\) 就应该是一个一次函数 \(k_v\times x+b_v\) 的值；而 \(v\) 的一个儿子 \(w\) 的 \(E(w)\) 就应该是 \(k_w\times E(v)+b_w\) 的值。换言之我们是在自上往下不断把 \(x\) 替换为关于 \(x\) 的一个一次函数。
把这个一次函数称作一次变换：定义 \(FG(x)\) 表示 \(G(F(x))\)（对于更多个一次函数也同理）。那我们的 \(E(u)\) 就是：把 \(s\rightarrow u\) 的路径上的点 \(v_1,v_2,...,v_k\) 依次写出来，那就是 \(E(u)=F_{v_1}F_{v_2}...F_{v_{k}}(x)\) 。
当我们换根 \(s\rightarrow v\) 的时候，假如 \(u\) 是 \(v\) 子树内一点，则它对应的式子会少掉最后的一个变换 \(F_{1}\)。我们左乘上它的左逆 \((F_1)^{-1}\) 即可；假如 \(u\) 是 \(v\) 子树外一点，则它对应的式子会额外多出一个变换 \(F'\)，我们左乘上即可。
因此我们需要维护每个点的一个变换 \(F_i\)，并且支持区间把 \(F_i\) 变为 \(GF_i\)。注意到一次函数的复合是容易的，因此这也是容易的。
然后求树上路径的和，也就是在分别求树上路径的变换和，直接用树剖维护即可。时间复杂度 \(O(n\log^2 n)\)。
很高妙的图论题！
先来判断能不能让第一个人获胜。
首先可以注意到我们要么把边权设为 \(L\)，要么设为 \(R\)。我们不妨初始全部设为 \(R\)。
则第一个人要么已经能够获胜，否则我们必须调整一些边权。
我们能调整一条边 \(u\rightarrow v\) 从 \(R\) 变为 \(L\)，当且仅当第一个人到 \(u\) 的距离比第二个人到 \(v\) 的距离要近，这样的话：第二个人一定不会走这条边，否则第一个人也走这条边就已经赢了；那么我们为了让第一个人的最短路尽可能低，就把这条边设置成 \(L\)；否则，我们可以证明改这条边后不可能让答案变得更好：因为假设第一个人的路径走了这条边，第二个人也走一定会让第一个人无法获胜。
我们不断这样能调整就调整，最多调整 \(k\) 次后结束。如果无法获胜，用相同的手法判断能否平局。
时间复杂度 \(O((n+m)k\log n)\)。
怎么图论题都这么高妙。
我们先考虑关键点怎么求：显然其不强于什么 DAG 两点可达性，但是用 bitset 去维护定然会超时。
由于是 DAG，考虑研究拓扑排序相关的性质：一个性质是这样的点拓扑序一定固定。
那么我们可以随机若干个拓扑序，如果一个点始终位置不动就是关键点。
那么次关键点呢？多次随机判断其位置是否极差 \(\le 1\) 看上去很对，但实际上并不能通过：理由是一些非次关键点在随机找拓扑序的时候非常难以被区分出来，构造方式可以大家自己想一下：只要让一车它走不到也不能被走到的点，以极大的概率一定出现在这个点之前（或之后）就可以了。
考虑一些确定性的做法：对于关键点，在拓扑排序中它永远是单独出现在当前队列的。
这个条件必要而不充分：我们研究样例 \(1\) 就会发现，如果先删去 \(6\)，则 \(2\) 也会在拓扑序始终单独出现在当前队列里。看上去我们陷入了死胡同。
注意到此时还有一个性质：就是没有入队的所有点都能被队列里的这个唯一点走到；而反之其余的所有点一定不能被队列里的唯一点走到。
那么我们正反各拓扑一次，分别可以算出这些点能走到的点（以及能被走到的点），如果相加起来为 \(n-1\) 那么这个点就是关键的；此时我们找到了描述关键点性质的充要条件。
那么次关键点呢？我们还是考虑做两次拓扑，每次都找到一个点能到达多少个点。但此时队列大小为 \(2\) 并不意味着这两个点不合法：有可能对于其中一个点来说，删去这个队列里另外一个点，它就是合法的。
假设队列两个点是 \((u,v)\)，如何判断删去 \(v\) 以后 \(u\) 是合法的？首先不能有两个时刻队列大小都为 \(2\) 且分别出现 \((u,v),(u,w)\)；否则我们假设删去 \(v\) 以后还有一个点 \(w\) 不能被 \(u\) 走到：考察所有这样的点 \(w\)，必定有一个能被 \(v\) 直接走到：那么我们只需要考察 \(v\) 的所有后继，是否此时只和 \(v\) 有连边即可。
这样就在 \(O(n+m)\) 的时间内完成了检查。
感觉这个题还是非常思维的。
神题！
发现样例是把所有边全选上了，所以我们猜测一定能选满。也就是给定任何一张图都能构造的意思。
先考虑 \(k=2\) 的情况：发现是经典欧拉回路问题：对于奇数点我们将其和虚拟点 \(0\) 连边，然后对每个连通块都跑欧拉回路，按顺序依次交替分别 \(1,2\) 两种颜色，最后删掉虚边。可以证明这样就让每个点的两种颜色差 \(\le 2\)。
如果一个点不是回路的起点，它进入一次，紧接着就会出去；那么这两次的颜色是不同的。因此它的颜色相等。
否则这个点会走若干个次环路。如果走偶环，则出去和进来的颜色是不同的；如果是奇环，则进来和出去的颜色是相同的。但是我们注意到假如连着走了两个奇环，那么如果第一个奇环两次都是 \(1\)，第二个奇环两次就会是 \(2\)；这样相差 \(2\)。
那么再考虑删除的虚边：注意到只有原本奇数度数点才会删除一条边，而此时他和 \(0\) 连通，我们一定是用 \(0\) 作为起点的，因此这个点不是起点 $\rightarrow $ 原本两种颜色数量相等 $\rightarrow $ 删去一条边后两种颜色差 \(1\)。
这样我们完成了 \(k=2\) 的构造。对于一般情况：我们考虑任意给图染色，然后不断找到一个不合法的点 \(u\)：把他的最大颜色和最小颜色 \(x,y\) 拿出来，用 \(k=2\) 的方法调整所有 \(x,y\) 两种颜色的边。不断调整，则最后一定能调整出一组合法解。
为了优化效率：考虑初始随机染色，这样需要调整的对就不会太多，可以轻松通过。
非常神仙的构造！并且 sjy 的解法也非常优秀。
考虑用补图来描述：也就是如果 \(\gcd=1\) 我们连边。
则我们要么找一个大小为 \(k\) 的独立集；要么找一个没有孤点的大小为 \(k\) 的导出子图。
直接贪心！从前往后能加就加；如果有大小为 \(\ge k\) 的独立集直接赢麻，否则我们的独立集有 \(a\lt k\) 个点，剩余的每个点都至少和独立集的一个点有连边。把点分成 \(a\) 类，注意到 \(2a\lt n\) 因此必定有一类至少有三个人。我们按照类的大小贪心从大往小考虑，考虑第一次前缀和 \(\ge k\) 的位置，如果最后一个选的类至少选出了两个则我们就找到了一组解；否则我们把第一组少选一个，第二组多选一个即可。这样我们一定找到了解。也就得到了一个 \(n^2\) 级别的构造方式。
现在来考虑如何加速过程：首先是判断能不能加入一个点进入独立集，那就是给一个集合，支持加数，以及给一个数问有多少个互质的。这个直接莫反：可以做到 \(d(a)\)，由于只关心是否互质所以可以进一步做到 \(2^{\omega(a)}\)。
再来考虑 \(n-a\) 个人会归于哪一类：套用上面的操作，直接整体二分即可。
这样时间复杂度 \(O(n\log n\times 2^{\omega})\)。常数很小。
先不考虑 \(R\) 的限制：我们从大往小考虑每条边，在生成树中加入它，并且删去原树上两点路径的最大边即可，这样在 \(O(nm)\) 的时间内维护出了每个 \(L\) 对应的 MST。
考虑现在还有边权 \(\le R\) 的限制：因此我们对每个时刻维护一颗 seg，删除/加入某条边的时候在 seg 对应位置修改；使用主席树即可。
时间复杂度 \(O(m(n+\log))\)。
我去，有向图哈密顿回路。
怎么 \(m\le n+20\) 呀？
注意到：如果有一个点 \(u\)，出度为 \(1\)，则设其连向 \(v\)：当我们走到 \(u\) 的时候，下一步必须立刻走 \(v\)，因此我们删掉 \(v\) 的其它入度，然后把 \(u,v\) 合并成一个点；类似地，如果 \(u\) 入度为 \(1\)，我们做相同的事情。
则最后要么只剩一个点，要么每个点出入度都为 \(2\)。
如果真的有哈密顿回路：则考虑如下构造，在一个环（也就是最后的答案基础上）加若干根弦，这样的话每条弦能让一个点的出度加一，一个点的入度加一；最多只能让 \(20\) 个点出入度为 \(2\)。
然后我们状压即可。令 \(v=m-n\)，则复杂度 \(O(2^v\times v^2)\)，可以轻松通过。
非常好的构造题。
假如我们能让两个格子的若干个数分别都是有序的（同时升序/降序），那我们选择一个他们都能走到的格子，然后就可以把两个序列归并起来。
考虑对于一个格子 \((i,j)\) 而言，可以把所有满足 \(x\le i,y\le j\) 且 \((x,y) \neq (i,j)\) 的格子的序列都归并到这个位置。
因此我们设 \(f(i,j)\) 是能把多少个格子移动到 \((i,j)\)，则有 \(f(i,j)=\sum_{(x,y)\lt(i,j)}f(x,y)\)。
初始 \(f(1,1)=1\)。那么计算一下只能排序约 \(2.5\times 10^4\) 个盘子。但是注意到我们此时每次只动了一个盘子。考虑每次动多个盘子会发生什么。
我们发现 \(f(1,2)=f(2,1)=1\)。但是我们可以做到令其为 \(2\)：如果我们把两个按顺序取出就是我们想要的顺序，则直接全部一起取出，否则分两次取出即可。
这样 \(f(6,6)\) 就大于 \(4\times 10^4\) 了，可以通过本题。
操作步数是不超过 \(10n\) 的。
很清新的好题。
注意到根据题目限制：任何时刻，一个糖的出现次数上下界 \(L,R\) 相差不超过 \(1\)。
我们考虑满足从前往后扫描每个时刻，如果有糖原本 \(cnt=L\)，这个时刻 \(L\) 增加了，则如果有多个一定失败，否则我们这一天必须选这个糖；否则我们一定选择一个 \(cnt=L\) 且 \(L=R-1\) 的人，如果没有一定失败，否则我们会选择 \(L\) 增加的时间最靠前的那个人，正确性容易证明。
上述过程可以拿堆维护。注意到由于 \(\sum R\) 是和天数同阶的，所以总的变化次数和天数也是同阶的。
我们猜测存在一个阈值 \(V\)，一旦天数大于这个，就一定能无限下去。
令 \(V=10^6\) 发现已经可以通过，我们来分析一下其中的道理：当天数是 \(\sum a\) 的倍数的时候，注意到每个人的 \(L,R\) 都是相等的，也就是得到了一组确定的解。
只要我们的天数里有两次都是 \(\sum a\) 的倍数，我们就肯定能不断重复这段时间内的操作无穷做下去。
注意到 \(\sum a \le 10^5\)，因此其实 \(V=10^5\) 就可以了。
一万年没更新做题记录了，先写个厉害题的。
考虑大概算法应该就是：树上带根连通块套用 dfs 序 dp 的套路，问题是我们好像都不太会快速判一个串是否出现过，考虑那就大概是个 dp 套 dp 的过程。
所以如果能解决判定一个串是否出现过这个题就应该是做完了，并且我们知道大概他就是用 dp 的方式去判。
观察一下 \(a\) 序列，会发现只有末位是在跳的，去除末位的话这是一个相邻两项差不超过 \(1\) 的递增序列。
也是容易证明的：因为我们 \(a_n\rightarrow a_{n+1}\) 最多加 \(k-1\)，也就是至多进位一次。
这点是本题的突破口：末位和末位以外的部分有本质区别，也就是我们判定一个串是否出现，它的前 \(len-1\) 位一定是出现过的，唯一的问题就是末位可能会对不上。
因此考虑把前 \(len-1\) 位喂给我们的检查函数，然后得到最后的可能的那些末位集合，再判我们询问串的末位是否出现在这个集合里，这个长得就非常有自动机的那种感觉。
我们来研究前 \(len-1\) 的变化，如果是每次 \(+1\) 那其实挺麻烦的：因为我们是关注这里的最大数位的，但是你 \(+1\) 后最大数位不太能维护。
所以从低位开始喂数字不太可行，考虑从高位开始喂：就是我们可以设 \(dp(i,j,k,l)\) 表示现在第 \(2\sim i\) 位都是 \(0\)，然后 \(i+1\) 往后的位里的最大数位是 \(j\)，目前的末位是 \(k\)，我们不断增加，第一次让第 \(i\) 位变成 \(l\)，且 \(2\sim (i-1)\) 位都是 \(0\) 的时刻，此时的末位是多少。
那我们其实就是先让第 \(i\) 位变成 \(l-1\)，因此 \(k:=dp(i,j,k,l-1)\)；然后先让 \(i-1\) 位变成 \(k-1\)，再让 \(i-2\) 位变成 \((k-1)\)，。。。，直到 \(2\sim (i-1)\) 位都变成 \(k-1\) 了，然后此时我们再不断在末位加数使得最后产生一次进位。直接利用之前算出来的 dp 值维护过程中的 \(k\) 的变化即可！
这个 dp 朴素做大概是 \(n^2k^3\) 的，但是比较容易优化到 \(nk^3\)。
那么回到本题我们把这个过程套进 dfs 序上就好了，也就是 \(f(u,i,j,k)\) 表示目前到了 \(u\)，然后还要填 \(i\) 个位置，前面的最大值是 \(j\)，当前的末位是 \(k\) 的方案数。这部分是 \(n^2k^2\) 的。
因此总复杂度 \(O(nk^3 + n^2k^2)\)。