1101总结
T1
不像是有低于 \(O(n\sqrt{n})\) 做法的题，上莫队。
题解说 \(O(n\sqrt n\log n)\) 过不了是它写得太烂了，肯定是可以过的。
但是考虑到查询次数为 \(O(\sqrt n)\)， 于是用分块维护就行了。
复杂度 \(O(n\sqrt n)\)，其实进一步观察，发现每次前缀和数组的变换量是 \(O(1)\) 的，分块都可以省了。
\(n,m\) 不要写反，对询问排序的时候 \(n,m\) 写反喜提 WA。
T2
很难的题，我不会。
My Method
先得想到它是个构造排列的计数题，直接做哈密顿路径题太过困难了。
构造排列的计数题往往有这些考虑方式：按元素值从小到大考虑构造，按排列下标从小到大构造，以插入元素的方式构造。
以插入元素的方式构造，往往可以按某个外部值排序，经过这个排序之后再来插入，得到理想的结果。
这道题是第三种方式，但是我不是很熟悉这种方式。
转化一下题意，你需要构造一个排列 \(p\)，排列元素的值代表下标，排列顺序代表遍历顺序，需要满足序列的限制条件。
考虑大力动态规划，插入了限制序列下标为 \([1,i]\)，有 \(j\) 个位置不满足条件（R
限制，L 限制必须在插入前满足。）的方案总数为 \(dp[i][j]\)，转移可能还需要记最后一个是否是
R，可以 \(O(n^2)\)
的算出总方案数。
考虑计算以每一个下标结尾的答案，那么在对应位置处需要钦定必须放在最后面，其余的可以正常做，仍然需要讨论倒数第二个到底放的什么，但是动态规划过程中无需记录，只需要讨论最后到底是
R 或 L。
发现我们的计算过程可以等价于一个行向量乘上若干个矩阵再乘上一个列向量。
可以 \(O(n^2)\) 的算出前缀行向量和后缀列向量。因为转移参数和前缀 R 的个数有关，所以还得讨论选择的合并中心是 L 或是 R 。然后 \(O(n)\) 的合并。
复杂度为 \(O(n^2)\)。
Solution
题解做法比我高明的一点在于它将第二维记录的信息从简单的 “不合法”
拓展到 “路径条数”，表达力更强，合并起来也更容易理解，同时 DP
的转移矩阵和前缀 R
的个数失去了联系，因为被蕴含在了路径条数这一信息中。
T3
很趣味的题，首先有一个暴力，考虑求出变换后的所有边。
分解样例，猜想答案是一个乘积的形式。
考虑一条边的限制，发现从小到大不太好做，因为对大的有限制的点之间是没有关系的，然后就从大到小做，发现对小的有限制的点必定相互限制，因此第 \(i\) 个元素的贡献就是后面所有 \(n-限制它的点的个数\)，由此也容易证明答案确实是一个乘积形式。
问题变成了求一个点被比它大的哪些点限制，场上没时间了就没想了。
实际上很简单的，直接从小到大合并上来就行，做启发式合并，用并查集去重（一个点如果被合并了，那么就属于较大的那个点，然后另一个点尝试合并它的时候就合并较大那个点），需要把小于等于 \(i\) 的点动态删掉。
复杂度 \(O(n\log^2 n)\)
T4
博弈题，考虑先手必胜的充要条件，直径为 \(2\) 先手必败，考虑直径大于 \(2\) 的所有情况，发现如果选不是叶子的点，每次扔掉所有叶子后直径会减二，如果选直径上的叶子，那直径只会减一，所以一个人可以将一个数减一或者减二。巴什博弈。
问题变成了给根和子树求直径，先搞出以一为根的所有情况，如果根在子树外，输出答案，如果在子树内，那就是向根走一个点之后那个点的 \(from[u]\) 值，很好算。
但是喜提 WA，因为根在当前点是答案是整颗树的答案。
换根问题总共有三种情况：根在子树内，根在子树外，根就是这个点。