这题允许离线！

我们把每个第二类修改操作的界限定一下，然后对下标轴扫描线。显然先做完所有修改再询问答案不变。

对于不存在的点，其存在也无妨，只不过不能生长了而已。

那么每次操作的实质就是把一段区间内所有点的父亲都给改变。

考虑对这个区间改父亲的操作进行根号分治，如果更新的区间长度大于 $B$ 那么就懒惰改父亲，否则在 LCT 上暴力改父亲。

这样，我们每次 LCT 的总操作次数不会超过 $O(B)$ 次，该部分复杂度为 $O(B\log n)$ 的。

对于查询，我们发现最多跳 $O(n/B)$ 个懒惰加的父亲到达根节点，该部分的复杂度即为 $O(n/B+\log n)$ 的。

这样，我们稍微平衡一下，取 $B=\sqrt{n/\log n}$，就得到单次复杂度为 $O(\sqrt{n\log n})$。

总复杂度 $O(q\sqrt{n\log n})$。

这个做法可能有点暴力，使用改点权的技巧可以做到 $O(q\log n)$。不过太难写就算了。

参考代码。