主要思路
刚开始以为是搞\(\log n\)个基底点，然后双向边上面做事情，最后发现找图上最小环的复杂度非常的高。所以 GG。
正解考虑把问题的规模进行缩小：也就是把一些答案预先特判掉。比如说，如果某一个位上有超过三个点连接，那么环的大小就可以被确定为是\(3\)，也就是最小的可能。考虑超出\(3 \times 60\)这么多就可以直接判定答案为\(3\)。
再考虑剩下的情况。此时，\(n\)已经缩小了很多，所以我们暴力建图，用 Floyd 跑最小环即可。
刚开始以为是搞\(\log n\)个基底点，然后双向边上面做事情，最后发现找图上最小环的复杂度非常的高。所以 GG。
正解考虑把问题的规模进行缩小：也就是把一些答案预先特判掉。比如说，如果某一个位上有超过三个点连接，那么环的大小就可以被确定为是\(3\)，也就是最小的可能。考虑超出\(3 \times 60\)这么多就可以直接判定答案为\(3\)。
再考虑剩下的情况。此时，\(n\)已经缩小了很多，所以我们暴力建图，用 Floyd 跑最小环即可。
这道题是一道好题。
我们可以直接暴力 DP，考虑状态\(dp[i][j]\)为\(i\)个\(1\)与\(j\)个\(-1\)的答案。那么，我们可以从少一个\(1\)的情况和少一个\(-1\)的情况进行转移：
一定要思考，不能想当然。这句话是说给我听的。
把连通块连边，每一次 BFS 扩展就算做一次点击，然后\(O(n^2)\)确定路径长度，再按奇偶性判断就行了。
思考量很小的一道题。
先用间接法来算。初始答案为\(n!\)，然后考虑容斥掉那些符合排序规则的方案。发现，我们可以分开来考虑，按照容斥的顺序：先考虑只算第一维、第二维的，在加回来两维都考虑的。
第一维和第二维的做法非常显然：排序之后用多重集的排列就行了，考虑每一个相同的区间里面内部乘起来。如果有\(k\)个连续的数段，那么部分的答案就是\(\prod_{i = 1}^l len_k!\)。
做过 LCT 么？（做过基本上就可以切这一道题）
考虑把跟节点先去掉，然后会产生很多个联通块：每一个连通块求出最小生成树，然后找到整个连通块与根节点连接的最小边，连上。
之后如果还剩下一定的可以使用的度数，我们可以考虑用根节点剩余的边去更新整个最小生成树。具体而言，我们找到了一个\((1, v)\)未使用的边，然后我们找\(1 \to v\)上所有的边，找到一个差值最大的。如果这个差值是正数，那么加入这条边，删去之前的边，就会发现答案减掉了这个正差值。不停重复就可以得到答案。