by Duck.
感觉都是神秘乱搞。一般的处理方式：
- 把整个环当成根。
- 断环。
CF711D Directed Roads
正难则反，考虑统计成环的数量。
我们先把环搜出来，那么环上的边只能有全部顺时针或者全部逆时针两种方向，环外的边任意。
设环长为 \(L\)，那么就有 \(2^{n-L}\times 2\) 种有环的情况，从而有 \(2^n-2^{n-L+1}\) 种没有环的情况。对每个连通块分别处理，乘起来即可。
时间复杂度 \(\mathcal{O}(n \log n)\)。
CF835F Roads in the Kingdom
把环当作根，相当于一个环上挂了好多子树。先处理出每个子树的直径，以及其到子树的根的最长链。
给环钦定一个开头，看成一条链加上一条连接首尾的边。每个点的子树中的最长链作为这个点的点权，那么答案就是 \(\min\{w_i+w_j+\text{dist}(i,j)\}\)。
考虑断掉一条边的影响。\(i,j\) 有可能被同时划分到这条边的前缀或后缀，这样可以递推。以前缀为例，从小到大考虑到 \(i\)，维护前缀 \(w_j+\text{dist}(j,i)\) 的最大值，只需要从 \(w_j+\text{dist}(j,i-1)+e_{i-1,i}\) 转移过来。
如果 \(i,j\) 被切到了两边，那么就需要走连接首尾的边连起来。这时候需要维护前缀 \(w_j+\text{dist}(1,j)\) 的最大值以及后缀 \(w_j+\text{dist}(j,n)\) 的最大值。拼起来加上 \(e_{1,n}\) 即可。
时间复杂度 \(\mathcal{O}(n)\)。
P1399 [NOI2013] 快餐店
双倍经验，只需要取直径的中点即可，输出直径长度除以 \(2\)。
时间复杂度 \(\mathcal{O}(n)\)。
P4381 [IOI2008] Island
三倍经验，只需要把每个连通块的最长链串起来，改一改 \(\min/\max\) 之类的细节即可。
时间复杂度 \(\mathcal{O}(n)\)。
P2081 [NOI2012] 迷失游乐园
[AGC004F] Namori
神仙思维题。
可以发现 \(n\) 为奇数一定无解。因为最后每个点都会被反色奇数次，而一次操作会把两个点同时反色。无论如何，最后的总操作次数都是偶数。如果 \(n\) 为奇数，则总操作次数为奇数，矛盾。
先从树的情况入手，考虑按照深度的奇偶性进行二分图染色，那么一次操作只会同时操作一个黑点和一个白点，并且会将这两个点反色。我们的目标是将所有黑点变成白点，白点变成黑点。从这里也能看出，如果黑白点数量不相等，那么就无解了。
接下来求最小操作次数。考察每条边，设其子树内黑白点之差为 \(a_i\)，我们希望最终黑白点之差变成 \(-a_i\)。而对这条边的一次操作会把一个点反色，也就是会把差值减小 \(2\)。所以这条边至少需要操作 \(|a_i|\) 次。
可以发现，\(\sum |a_i|\) 就是最小的答案了。自底向上从叶子开始构造，一定可以得到一个合法的过程。
接下来考虑基环树。延续二分图染色的思路，将基环树分为偶环和奇环。
对于偶环的情况，仍然是一个二分图。我们先断掉一条边，再考虑这条边能做出什么贡献。断边之后当成正常的树来处理，把整个环当作根，和树的区别在于环上的边可以改变方向。
设 \(x_i\) 表示环上第 \(i\) 条边的移动次数，正负表示方向，绝对值表示次数，那么可以得到一个线性方程组 \(\{x_i-x_{i+1}=a_i\}\)。
这个方程组没有唯一解，我们要最小化 \(\sum |x_i|\) 的值。不难发现这是一个经典题目糖果传递，将所有方程都表示为 \(x_1\) 之后，令 \(x_1\) 取中位数即可。
最后来考虑奇环。这时候不是二分图了，直接解方程组有点困难。考虑多出来的这条边，它会同时让两个黑点变成白点，或者同时让两个白点变成黑点，可以用这条边来补齐其他点的差异。能补 \(\frac{1}{2}\sum a_i\) 次，也就是给环上的每个点补齐这么多。此时如果 \(\sum a_i\) 为奇数就无解了
这样就都讨论清楚了。时间复杂度 \(\mathcal{O}(n \log n)\)。
[ARC140D] One to One
每个连通块都是基环树森林，从而我们可以将统计连通块转化为统计环。
先不考虑 \(a_i=-1\) 的连边，用并查集维护确定的边，那么此时每个连通块一定都是树或者基环树。同时对于每个是树的连通块，里面一定恰好有一个点的 \(a_i=-1\)。
考虑计算每个环在多少种方案中出现过，这样它就做了多少次贡献。
我们只关心环的贡献，此时树接基环树是不会有影响的，只有树之间连接才会产生新的环。设一共有 \(m\) 棵树，则一个基环树的贡献就是 \(n^{m}\)，可以先不管。
对于是树的连通块，考虑用 \(k\) 棵树串成一棵基环树，统计这个环的贡献。那么 \(k\) 的答案就是在 \(m\) 个 \(|V_i|\) 中选择 \(k\) 个数的乘积的和。这个东西是一个 dp 可以解决的，先放着。
但是我们只是选出来了 \(k\) 棵树串起来，还要钦定它们之间的顺序，这个东西就是圆排列，可以知道有 \((k-1)!\) 种方法。同时，其他 \(m-k\) 棵树可以任意连，方案数为 \(n^{m-k}\)。
考虑上面那个 dp，不难想到设 \(f(i,j)\) 表示前 \(i\) 个数选了 \(j\) 个的乘积之和，转移是容易的。
\[f(i,j)=f(i-1,j-1)\times |V_i|+f(i-1,j) \]这部分最后的答案就是：
\[\sum_{i=1}^m f(m,i)\times (i-1)!\times n^{m-i} \]时间复杂度 \(\mathcal{O}(n^2)\)。