经过同学的指点，发现F题有一只log的做法——点分树。

首先两个点在点分树上的lca一定在原树上这两个点的路径上。

所以我们把x-y的路径分成x-点分树上的lca 和 点分树上的lca-y的两条路径。

用树链剖分的方法维护一下点分树上的点到其他点的信息即可。