好久没写博客了（

这场打的很屎，遂记。

T1 树V图

上来没什么思路，然后打了暴力就run了，没去仔细想。

首先 $ f $ 相同的点肯定构成一个连通块，否则不合法，所以我们可以缩点，然后枚举 $ f_{i,j} $ 表示 $ a_i = j $ 时 $ i $ 及 $ i $ 子树内合法方案数 ，然后转移时去判一个方案合不合法，注意到对于两个 $ i $ 只需要判他们的交界处那两个点合不合法即可，所以可以直接暴力转移。时间复杂度是 $ O ( n^2 ) $ 的。

关于这个复杂度的证明，我们可以忽略第一维，因为 一个 $ j $ 必定只属于一个 $ i $ ，所以是 $ O ( n^2 ) $ 的。

T2 矩阵

这个题表面看起来比较好做，只需要维护每一行和每一列的平衡树，然后每次将相应的行和列进行交换即可，单次 $ O(n \log(n)) $ ，校内 OJ 给了 10 s ，洛谷 8 s，标算才 $ 1e8 $ ，这不轻松跑，然后直接写加调一个小时左右成功过掉小样例，然后把大样例扒出来一测，您猜怎么着，跑了 105 s，这是一个正常题该有的常数吗！

然后卡了一个半小时最终卡进 70 s，交上去还不如暴力分多。

那么这道题注定是有着巨大常数的，所以我们只能写 $ O(n^2) $ 的做法。

每次转移一行或一列，除了平衡树，还有 十字链表 能做这件事，但是但区间加并不好维护，那么我们考虑差分，这样每次改变的就只有八条边了，但是旋转怎么办呢，我们不可能去实施维护他上下左右是谁，不然就是暴力了。

考虑下面这种形式来表示他的四个方向上是谁：

一开始这个点未进行旋转， 0 指上面，然后我们把这点旋转了，指上面的应该是 1，如果旋转两次那就是 2，所以如果他旋转了 $ n $ 次，那么 $ n $ 指的就是上面，相对应的 $ n + x $ 对应着 $ x $ 方向，只需要给每个点打 tag 就行了，说白了还是区间加操作。

那么对于每次操作，我们暴力把涉及到的八条边找出来，然后暴力修改他们的差分值和四周是谁就行了。

难点在于卡常。

还有就是这个东西是不是直接用一字链表也行啊，就和平衡树一样，不仅好写而且常数小（我没写，纯口胡，如果有问题请告诉我）。

T3 拉丁方

比较神秘建议去看原题题解。

这题主要难在 应用 cf600f 的做法。

讲一下 cf600f 吧，一个结论是 他的答案必定是 最大的一个点的度数。

证一下：

设这个度数为 $ n $ 。

必要性显然。

对于充分性，我们设计一种构造方案，对于每次新加入的边 $ ( x \to y ) $ ，分别找出 $ x , y $ 对应边的颜色的 $ \operatorname{mex}{(x)} \operatorname{mex}{(y)} $ ，如果一样 ，那么直接把这条边染成这个颜色，如果不一样，我们强制染成 $ \operatorname{mex}{x} $ ，然后去看如果 $ y $ 和已经连的边冲突的话，我们就把那条边强制改成 $ \operatorname{mex}{y} $ ，如果还冲突就一直这样改直到不冲突，我们整一下为什么这是合法的。

相当于证明这样去跑不会成环，首先成环肯定是偶环，因为这是二分图。

第一种，整个路径成环：

像这样，我们想把 $ (x \to y ) $ 染成 1 ，但是这和 $ y $ 的一条边冲突，把它改成 0 ，又会冲突，一路改下去，改到了 $ x $ 这，这种情况并不合法，因为 1 是 $ \operatorname{mex}{x} $ 所以不应该有和 $ x $ 连的 1 颜色的边。

第二种，中间有一个环：

这种也不会成立，因为红色的那个点已经染了两条 1 的边。

证毕。

所以这种构造方法可以找到颜色为 $ n $ 的方案。

然后 拉丁方这道题就是套用了两次这个，具体还是去看该题题解吧。