首先显然等他们都走到环上就行。那之后答案不变。
考虑修改操作。
所有操作肯定连成一个联通块，讨论这个联通块上的环是人造的还是天然的。
人造环可以发现一定是自环，且其他连接上的联通块位置无关，只需要是拆环连上去就行。
考虑天然环，枚举这个天然环是谁，其他联通块修改一条边连上去。
0：只有大小为1或2的环，二分染色即可知道连接到二元环的贡献，随后直接贪心即可。
1：是一个排列，只有环。显然若核心是自然环，一定取最小环，一定将最大的环连接上去。
2，3，4：
考虑连接自然环的拆环。发现一定拆环边而不是树边。
连接上去的贡献只需要取环上最多人的点即可。
到这里直接暴力自然环，复杂度已经是O（N^2）。
5，6，7，8，9：
考虑每一次拆开下一条环边时贡献的变化。发现就是把原本的环头带着连接的树节点放到环尾。
所以每次修改可以O(子树点数)。每个联通块对天然环的最大贡献可以O(联通块点数)计算得到。
联通块的选择可以排个序贪心。（可以计数排序）所以每次枚举自然环后乘上的复杂度是O(n)。
发现天然环具体是谁对于联通块贡献效果是无关的，只与天然环长度有关。而长度最多只有O(sqrt(n))种。
因此枚举可能的环长，O(n)求出所有联通块的贡献，把贡献最大的的环长等于目前枚举值的拿走作为自然环，剩下的贪心即可。
总复杂度O(n^1.5)