1863G

洛谷传送门 CF 传送门 看到 \(a_{a_i}\) 和 \(a_i \in [1, n]\)，果断连边 \(i \to a_i\)，得到内向基环森林。 那么每次相当于把 \(a_i\) 变成自环，连边 \(i \to a_{a_i}\)。 但是每次操作都改变图的形态很不好办，考虑打标记。 每次 ......

简洁的题面，深邃的思想。 首先，一个经典的套路是： 对于序列中涉及到对于 \(a_{a_i}\) 和 \(a_i\) 进行操作的问题，一般可以考虑建立 \((i,a_i)\) 的内向基环树或者 \((a_i,i)\) 的外向基环树转化为图论问题。 我们建立 \((i,a_i)\) 的内向基环树，\( ......

看成内向基环森林，操作 $u\to v$ 相当于让 $u$ 连向 $v$ 所连的点，$v$ 变成自环。发现如果一个点 $v$ 变成了自环，那么操作任意一个 $u\to v$ 都没有用。 从简单的情形出发，对于一个内向树（或者说环大小为 $1$ 的内向基环树），每次操作 $x\to fa_x$ 时，相 ......