树的结构随机时，树的深度为$O(logn)$，以某个点开始的一段连续区间lca变化次数不超过树的深度$O(logn)$

然后就可以利用类似P4435的做法做到$O(nlogn^2)$

不过对于不随机的树结构，例如特殊性质A，显然会被卡

不知道如果赛时写这个做法能得几分，遗憾没来得及写