如果你使用线段树分治，也许是如下两种情况：

• 详见这个帖子：https://www.luogu.com.cn/discuss/845308

• 可撤销并查集并不需要记录路径，如下：

//不是这样
int Getfa(int x){return x==Fa[x]?x:Fa[x]=Getfa(Fa[x]);}
//而是这样
int Getfa(int x){return x==Fa[x]?x:Getfa(Fa[x]);}