A. Hey, Have You Seen My Kangaroo?
考虑每次只关注一只袋鼠的运动路径，不难发现到最后袋鼠的路径一定是成环的，因为我们只需考虑每个周期最后袋鼠处在什么位置，若是有两个周期后袋鼠处在用一个位置，那么说明这一段时间内袋鼠一只在这个环上运动。
那我们不妨先考虑每次经过一个整周期的变化，暴力求出每个点一个周期后的对应点并向其连边，而每个点都有且仅有一条出边，说明这是一颗内向基环树，不在环上的点最多只会有最大深度个周期时存在袋鼠，而环上的则每个周期过后都有袋鼠。并且我们还能得到，由于袋鼠是稠密的，每个周期后存在袋鼠的点是上一个周期的点的子集。
这些性质有什么用呢？再来尝试考虑单个时刻的变化，一个很关键的考察是我们不去考虑每个时刻的答案，而由于答案变化仅在袋鼠合并时发生，且这是不可逆的，因此我们去考虑什么时候两只袋鼠发生了合并。
暴力模拟一个周期内袋鼠的移动，若是两只袋鼠发生了合并，则答案减 1，而由于上述性质，这样的减 1 只在一个前缀发生，且不会发生我们模拟到的这些减 1 之外的减 1 行为。换句话说，我们只需考察这样的行为何时会发生。不难发现这个时刻其实是好求的，就是基环树上两个点深度最大值取 \(\min\)。合并过后新的点则是两个点的最大值 \(\max\)，一直模拟上述整个周期的过程，求答案就只用简单地把这些 -1 做前缀和。
B. Birthday Gift
很厉害的构造题！我不会做...，如果你直接贪心地把能删的先都删了，会发现最后选取 2 的结果很难刻画。而其他方法又不是很走得通，因此只能想一些巧妙的转换。
接下来这步感觉非常 Ad-hoc，由于每次删数不改变位置奇偶性质，因此如果我们把奇数位上的数 reverse 并一直合并 01，最后就只会剩下一种颜色，直接用 2 补充少的那边即可。
C. Topology
挺厉害的 dp 题，转移过程值得深究，题解写的一坨，感觉完全就是错的。
考虑常见的关于拓扑序的几个刻画：每次拓展一个带根联通块的一个序列；每次将儿子序列归并得到的序列，分别对应从根到底和从底到根。如果从第二种刻画入手，你就需要对每个点做到根的树上背包，而且这玩意很难优化，因此我们尝试去用 dp 描述第一种刻画。
设 \(f_{x,i}\) 表示目前已经确定了 \(x\) 的子树外所有节点在拓扑序中的相对顺序，\(x\) 排在上述点中第 \(i\) 位的方案，但是你会发现这样转移还是三方的，因为你每次还要加一维表示额外位移，因此考虑设成 \(x\) 排在整个拓扑序中第 \(i\) 位的方案，当我们从 \(f_{x,i}\) 转移到孩子 \(f_{v,j}\) 时，需要乘上除 \(v\) 外其他节点的拓扑序并将其与之前排在 \(i\) 之后的点归并，转移柿子形如 \(f_{x,i} \times \binom{n-(i-1)-siz_v}{siz_x-siz_v-1} \times g_{S_x \setminus S_v}\rightarrow f_{v,j}\)，其中 \(g\) 是子树拓扑序方案。
注意你需要格外小心 dp 柿子的定义，否则可能会提前安排了子树内的方案导致选 \(j\) 变得不合法。
D. Toe-Tac-Tics
你先别急。
E. Left Shifting 3
按照题意模拟即可。
F. Subway
暴力建图是 \(O(n^2)\) 的，因为可能有很多地铁路径同时经过一个点，此时你两两连边就会爆，不过其他地方的边数是正常的，因此你主要考虑的就是怎么优化这个地方的转移。
考虑 dijkstra 的过程：每次从队列里取出一个 dis 最小的点去更新别的点，在上述情况中有很多更新可能是没用的，又由于这个贡献形式很特殊，长得很像一次函数，我们不妨考虑反过来，每次找一个点接受所有已经出队了的点的转移。这个点该怎么找比较好呢？不难发现贪心地选 \(a_i\) 比较小的点一定是更优的，因为我们不可能用这条边有效地更新了其他点再用其他点反着更新回来，这之中第一条边权就已经超了前面需要的总花费。
那我们怎么实现这个过程呢？其实很简单，由于贡献是一次函数，每次 dijkstra 出队的时候把对应直线加到李超树里，然后用目前的信息转移还没出队的 \(a_i\) 最小的点即可。
G. Binary Tree
考察通过这个询问你可以获得什么信息，不难发现这相当于把目标点的可能位置拆到了 \(\text{lca}\) 处朝向 \(u\) 或 \(v\) 的两棵子树或其他点，每次选重心作 \(\text{lca}\) 显然最优，因此套淀粉质上去即可，还要额外注意每次必须选两个 \(\text{siz}\) 最大的，否则常数不对可能会出问题。
H. Border Jump 2
你先别急。
I. Bingo
很套路的题，用正常的容斥思路去想是完全可以的，题解的 \(\min - \max\) 容斥和这个本质相同，但是有点大材小用了。
算所有情况最小值的总和，转化成算有多少种情况的最小值大于 \(0,1,2,\cdots,n-1\)，再做一手容斥，变成钦定若干行若干列必须小于等于 \(k\) 并计算方案再乘容斥系数，对于一个 \(k\) 列出柿子大概就是：
\[\sum_{i=1}^n \sum_{j=1}^m (-1)^{i+j} \binom{n}{i} \binom{m}{j} (a_k - a_{k-1}) \binom{c_k}{mi+nj-ij}(mi+nj-ij)!(nm-mi-nj+ij)! \]其中 \(a_i\) 和 \(c_i\) 分别表示第 \(i\) 大的值和种类数，式子看着长，自己推一推还是很简单的。
直接做是三方的，考虑化简一下，后面的一串式子比较烦人，我们设 \(d=mi+nj-ij\)，交换一下求和顺序，可以得到：
\[\sum_{d=1}^{nm} \sum_{k} (a_k - a_{k-1}) \binom{c_k}{d} \sum_{i=1}^n \sum_{j=1}^m [mi+nj-ij=d] d! (nm-d)!(-1)^{i+j} \]后面的部分和 \(k\) 无关，直接枚举 \(i\) 和 \(j\) 预处理即可，于是只剩下一项组合数和两边都有关，拆开发现就是只关于 \(d\) 的卷上一项 \(\frac{1}{i!}\)，NTT 优化即可。
J. Social Media
随便建边模拟一下即可。
K. Strips
挺有意思的小清新 dp，对每个没被分开的连续段分别做，记一个 dp 表示覆盖 \(i\) 之前所有点的最少纸条和最近向前延伸的距离，简单转移即可。
L. P⊕Q=R
你先别急。
M. Ordainer of Inexorable Judgment
计算几何，skip 了。
标签：袋鼠,周期,3rd,16,sum,mi,每次,考虑,Universal From： https://www.cnblogs.com/eastcloud/p/18568930