建出笛卡尔树。则两种边分别连向 $i$ 的父亲，以及 $i$ 第一个拐弯的祖先。

尝试对每个节点维护出子树内每个点到自己的距离。DFS + 线段树。先对子树整体 $+1$。需要进行一些修正。需要修正的是那些最短路中上一个节点在 $x$ 的左儿子的右链中或者右儿子的左链中的点。可以暴力枚举两条链上的点，是 $O(N)$ 的。

这里定义一棵新树，在新树中每个节点以笛卡尔树有连边的点中较浅的点为父亲。有一个结论：新树中每个点的子树仍然是一个区间。那么修正就是进行若干的区间加操作。

考虑使用历史版本和来压缩线段树的信息。

问题在于怎么处理询问的区间。

发现笛卡尔树的中序遍历就是 $1\sim N$，只要按照这个顺序进行修改，询问的时候就可以直接差分。

做两遍，一遍先遍历左儿子，一遍先遍历右儿子，分别处理出两个儿子的贡献。

可以主席树也可以离线扫描线。

时间复杂度：$O(N\log N)$。