TCO2015 Round 3B CommutativeMapping
题意输入一个长度为 $n$ 的数组 $g_i$，满足 $g_i \in [1,n]$。现在问有多少个长度为 $n$ 的数组 $f_i$，满足：$f_i \in [1,n]$$g_{f_i} = f_{g_i}$$n \leq 5000$题解看到 $g$ 的定义，立马想到建图连边 $i \to g_i$，这样连出的是一个基环内向树森林。可以先从特殊情况开始考虑。基环树的特殊情况无非就是树（某个...
题意输入一个长度为 $n$ 的数组 $g_i$，满足 $g_i \in [1,n]$。现在问有多少个长度为 $n$ 的数组 $f_i$，满足：$f_i \in [1,n]$$g_{f_i} = f_{g_i}$$n \leq 5000$题解看到 $g$ 的定义，立马想到建图连边 $i \to g_i$，这样连出的是一个基环内向树森林。可以先从特殊情况开始考虑。基环树的特殊情况无非就是树（某个...
题目大意有一棵基环树，现在你需要从基环树上选择一条边被删除，满足： 1. 删除后形成的是一棵树（不是森林） 2. 删除后的直径尽量小并且求出最小可能的直径题解首先基环树求直径大家都会。。。Island 岛屿（虽然由于我太菜至今还没卡常成功） 然后这个题我们考虑如何删除一条边之后快速算出直径。 我们只考虑最长路径跨过环的情况（不跨过环的可以轻松处理） 对于每个子树做直径 dp 是必须的，然后我...