已经九月了......
拜谢阿兰赵大神。
首先考虑这个过程和 UNR D2T1 其实还挺像的：当执行 \(n-m+1\) 次操作后，最大的 \(m-1\) 个人一定会按大小顺序排在最后。所以我们先来考虑 \(k=n-m+1\) 的，然后容易发现 \(k\lt n-m+1\) 也能套用这个方法解决（我们不关注未被影响到的后缀）。
从 \(b\) 序列倒推 \(a\) 序列：\(b_0\) 一定是 \(a[0,m)\) 中的最小值，如果 \(b_1\lt b_0\)，则它只能放在 \(a_m\)，否则 \([0,m]\) 中去掉 \(b_0\) 的位置，剩下的位置它都能任意放置。如果 \(b_1\lt b_0\) 的基础上，\(b_2\lt b_0\) 也成立，那么 \(b_2\) 只能放在 \(a_{m+1}\)。
因此可以推出 \(b\) 的每个前缀最大值（除去最后 \(m-1\) 个）有 \(m\) 的贡献，其它位置有 \(1\) 的贡献。
这样我们解决了 \(k\le n-m+1\) 的情况，由于 \(k\) 很大，猜测有一定规律性存在。
手动模拟一下就会发现最后 \(m-1\) 个一定是形成一个整体在动，而且前面 \(n-m+1\) 个人的相对顺序不变，相当于围成了一个环，然后最大的 \(m-1\) 个人位于环上的一个空，每次操作一次，这 \(m-1\) 个人就集体移动到下一个空。
这样我们知道了这个环的形态，但我们还不知道最后的开头是谁。
继续手玩会发现 \(k=n-m+1\) 的时候假设序列开头是位置 \(0\)，那么再操作一次开头变成了位置 \(n-m+1\)，然后继续操作一段时间好像开头没有变，直到又操作了 \(n-m+1\) 次。所以是之后：每操作 \(n-m+1\) 次后，序列开头减小 \(m-1\)（下标模 \(n\) 意义下）。
我们逆向做这个过程，就能得到这个序列在 \(k=n-m+1\) 的时候的形态，然后就做完了。
时间复杂度 \(O(n)\)。
拜谢 zhk 大神。
首先考虑枚举一个人 \(i\) 算他的答案，然后钦定他的第 \(j\) 个属性最大。
则我们会在保证有解的情况下，尽量给他尽可能多的颜色 \(j\)：也就是假设他被发了一个颜色 \(k\neq j\)，而其他人有颜色 \(j\)，则交换这两张牌一定不劣。
而这个值也是很好算的，因为我们可以算出每个人还要发多少张牌 \(r_i\)，则第 \(i\) 个人此时会被发到 \(\min\{r_i,b_j\}\) 张牌颜色 \(j\) 的牌。
然后考虑二分答案，现在问题变成要把剩下的牌发完，使得除了第 \(i\) 个人以外，其他人的每种颜色的牌不能超过一个值 \(x\)，问能否发完。
由于颜色很少，考虑建出匹配或者网络流模型后，利用 Hall 定理之类的在 \(2^4\) 的复杂度内去 check。
现在左边有四种颜色，\(s\) 向他们的连边，容量就代表这种颜色还要发出去多少。右边有 \(n\) 个人，他们向 \(t\) 的连边，容量就代表他们还要被发多少张牌（第 \(i\) 个人的容量此时是要算的，其他人的容量初始就已经确定）。
然后颜色向人的连边是这样的：第 \(j\) 种颜色向第 \(k\) 个人的连边容量，如果 \(k = i\)，则就是 \(\infty\)，否则是 \(x-a_{k,j}\)，因此我们要保证 \(x\) 不小于所有的 \(a_{k,j}(k\neq i)\)，这是容易检查的。然后我们要求的就是这张图的最大流。
考虑这里由于边带容量且不方便拆点，所以 Hall 定理不方便检查。考虑这种二分图匹配，还可以直接求最小割：
我们暴力 \(2^4\) 枚举哪些 \(s\) 到颜色的边被删去。不妨设还有 \(c\) 个颜色没被删，此时考虑右部每个点 \(u\) 的贡献，设所有没被删的颜色的 \(a_u\) 之和是 \(s_u\)，则这个点的贡献就是 \(\min\{r_u,cx-s_u\}\)。
注意到对于每个 \(mask\) 和每个 \(u\)，存在一个分界点 \(lim\)，使得 \(x\lt lim\) 的时候，这个 \(\min\) 取后者；\(x\ge lim\) 的时候，这个 \(\min\) 取前者。预处理后，容易 \(O(\log)\) 单次对于一个 \(mask\) 和 \(x\)，计算所有 \(u\) 的贡献和。然后我们去掉 \(i\) 的贡献和（因为 \(r_i\) 发生了变化），算上它正确的贡献即可。
这样设有 \(k\) 个颜色，则我们需要在 \(O(n2^k\log)\) 的时间内预处理，使得我们能 \(O(\log)\) 单次计算贡献和；然后对每个人都求答案的时间复杂度就是 \(O(nk2^k\log^2)\) 的，一个 \(\log\) 是二分，另一个 \(\log\) 是每次算贡献和。
拜谢 cftm 大神。
可以观察到，lca 一定是从 \(1\) 开始的一条根链。
我们可以直接枚举这条链上的最深点 \(u\)，然后把 \(1\rightarrow u\) 的路径拉出来，链上的每个点都挂了若干颗子树。
\(n\) 个点有两个属性：颜色 \(c\) 和类型 \(t\)。\(c_u\) 表示它的第一个在链上的祖先是谁；\(t_u\) 表示 \(u\) 属于 \(c_u\) 的哪个儿子（如果 \(c_u=u\)，则 \(t_u\) 也等于 \(u\)）。
定义颜色 \(c\) 的大小关系等价于深度关系，然后我们开始把所有点按照颜色 \(c\) 排序，相同的归并在一起。且保证 \(t\) 相同的点不相邻。这个条件是充分不必要的：我们可以把一个点的位置提前，放到 \(c\) 更靠前的两个位置中间。
所以我们得到这样一种方式不重不漏的生成所有合法数列：从小到大考虑每个颜色 \(c\)，从中选出若干个提前插入前面的空位（每个空位只能插一个数），然后如果颜色 \(c\) 留下了 \(x\) 个，就新增 \(x\) 个空位：第 \(i\) 个颜色为 \(c\) 的点之前就是新增的第 \(i\) 个空位。如果一个空位没有填数，则它两边的点，\(t\) 不能相同。
为了保证 \(lca(p_{n-1},p_n) = u\)，我们必须保证最后一个颜色（也就是颜色 \(u\)）留下来了至少两个人。
有了这些转化，其实多项式做法已经比较明朗了：考虑设 \(h(u,x)\) 表示考虑了链上 \(1\rightarrow u\) 的点，然后后面共有 \(x\) 个人往前插空，这样的一个方案数。
为了转移 \(h\)，对链上的每个点，我们要算出这样一个东西：\(g(u,x,y)\) 表示考虑所有颜色为 \(u\) 的点，且有 \(x\) 个人忽略（忽略是因为他们会被移动到前面），且有 \(y\) 个人会插进来的方案数。预处理 \(g\) 后的，\(h\) 的转移是容易的。
为了计算 \(g\)，考虑做这样一个经典的 dp：从小到大考虑每个种类，然后设 \(dp(i,x,y)\) 是考虑完前 \(i\) 个种类，删了 \(x\) 个人，还有 \(y\) 个相邻的 \(t\) 相同的对，这样的一个方案数。转移就直接枚举下一个类删了几个人，然后用了多少个空满足原本相邻两个相同，用了多少个空满足原本相邻两个不同，做个插板就能转移了。
最后注意到我们不需要每次拉出一条链重新计算 \(h\)，边 dfs 一遍边算就行了。
时间复杂度不太会算，毛估估了一下应该不超过 \(O(n^6)\)，而且有一个 \(n^2\) 我感觉是 \(\sum deg^2\)，反正跑的很快！
标签：考虑,颜色,log,个人,然后,2023.9,我们 From： https://www.cnblogs.com/Cry-For-theMoon/p/17674907.html