A STring
操作这么多次。。显然能消的 ST 都没了变成了 TTT...TSSS...S 。不难发现其实就是括号匹配，直接拿栈匹配就行了。
B Minimum Sum
按最小值来分治即可。每次贡献就是左右两端长度加 $1$ 的乘积。
复杂度 $O(n\log n)$，需要预处理 ST 表。
C Tree Restoring
考虑这 $n$ 个数字中最大的，必然是直径长度。然后我们先把直径画出来：
不难发现，对于 $[\lceil\frac d 2\rceil,d]$ 的长度我们至少的有两个点，才能构造出直径。然后如果多于 $2$ ，比如需要多构造一个直径长度的点就可以像红色边那样挂一个点，如果需要构造多一个长度为 $3$ 可以在绿边位置挂一个点。所以这区间内的长度都可以有多于二任意多个。
但是如果像图上直径长度是偶数，那么发现长度是 $\frac d 2$ 的点只有一个，如果是奇数可以发现长度是 $\frac{d+1}{2}$ 有两个。这些点的个数是不能随意增加的。
小于 $\frac d 2$ 的点是必然构造不出来的。然后就做完了。
D ~K Perm Counting
原题。首先容斥成钦定 $k$ 个位置满足 $a_i - i = k$ 的排列数。
然后几乎就和 这里 的 T3 一致了。大概是按模 $k$ 分类后，可以发现就是求一个交错的二分图的完美匹配的方案数量，这个东西可以插板法算。大概推一下就对了。
最后可以 NTT 复杂度 $O(n\log n)$。
E Sugigma: The Showdown
神仙题。
首先捋清楚：先手跑，后手抓，先手在红树，后手在蓝树。
通过观察可以发现，如果存在一条红边连接 $u,v$ 满足 $u,v$ 在蓝树上的距离大于等于 $3$ ，那么只要先手跑到了 $u,v$ 中的一个，同时后手并没能在这回合内抓到它，接下来先手必然可以通过在 $u,v$ 左右横跳来使得后手永远抓不到它。因为在后手距离先手在蓝树上是 $1$ 的时候就可以通过红边让后手距离先手变成 $2$ ，可以无限循环这个过程。
我们假定这个游戏还没有进行到先手能够让游戏无限循环下去的状态。也就是说当前先手可以用的红边在蓝树上距离必然小于等于 $2$ 。然后我们考虑一个事实：以后手起点为蓝树的根，先手所在的点在蓝树上一定随时处在后手所在点的子树内。因为一定不会出现先手通过红边跨过后手所在的点的情况。红边在蓝树上的长度小于等于 $2$ ，如果跨过了那么后手必然可以一步到达当前先手的地方，这么跳还不如就待在原地。
在有了这个结论后，对于一个点 $u$ ，假定蓝树上这个点到根的距离是 $d$ ，这个点在红树上到根的距离是 $r$ ，如果有 $d \le r$ ，那么先手一定不会把棋子移动到这个点上。因为先手的棋子不会跨过后手的棋子，所以先手走了一步后，后手一定可以往先手所在的子树走一步。如果后手一直选择这么走，那么先手一定会在到达这个点之前或者到达这个点的时候就被后手截住了。如果正好到达这个点就会被截住，那么前一步还不如就不走这一步。所以相当于，先后在任何一次行动的时候都得保证 $d > r$ 。
所以我们可以 dfs 一次，算出哪些点是可以通过走的时候满足 $d > r$ 到达的，然后看看这里面是否存在前面说的导致无限循环的点存在。如果存在，答案就是 $-1$ ，如果不存在，那么答案就是这里面最大的 $d$ 的两倍。最优决策一定是走到 $d$ 最大的点然后开始原地等待。
感觉这题比 F 仙好多啊。。
F Many Easy Problems
注意第一个样例 $k=1$ 的时候答案是 $3$ 。。所以这题 subtree 的定义大概是一个导出子树的东西。。（开始看错了好久所以做不来）。
然后知道这个定义后，我们考虑对于固定的 $k$ 算边的贡献。一条边如果存在于这个 subtree 中就说明这个边两侧都有这 $k$ 个点之一。那么方案数量就是
也就是总共的方案数减去点在同一边的方案数量。最后答案还要加上 $\binom n k$ ，因为每个方案都只统计了边，边比点少 $1$ 。
然后这么写一发发现能过所有样例，于是考虑优化一下。发现模数是 NTT 模数（之前 T４ 用过了）所以考虑用多项式，发现非常显然可以优化。
考虑 $siz_u = i$ 的 $u$ 有 $t_i$ 个，那么要算的就是：
发现是个差卷积的形式。直接做即可。