https://www.luogu.com.cn/blog/yizhiming/solution-cf1801e

题解说是 $O(n\log n\alpha(n))$，但是

for(int i=K;i>=0;i--){
	if((k>>i)&1){
		k^=(1<<i);
		merge2(b,getfa(c,k),i);
		b = fa[i][b];
	}
}

这一步倍增 $O(\log n)$，$k$ 级祖先 $O(\log n)$，总共是 $O(\log^2 n)$ 的。