Luogu7446 [Ynoi2007] rfplca

题意：给定一棵 个点的有根树，以 为根。

树用如下方式给出：给出 ，保证 ，将 与 连边形成一棵树。

接下来有 次操作，操作有两种： - 1 l r x 令 。 - 2 u v 查询在当前的 数组构成的树上 的 LCA。

，时限 。

---

分块。

问题的模型有点类似弹飞绵羊。

对于每个块，维护从每个点进入时，离开该块后到达的位置。

若块上的整体加法达到了 ，那么任意跳一次就离开了块。

所以，我们对于前 次整体修改暴力重构，后面就只需要加法标记了。

接下来考虑查询。

类似倍增 LCA 等经典算法，先让较深的点向上跳，直到两点在同一块内，然后查看答案是否在块内，若是，暴力找出答案，否则两个点一起向上跳。

块内存在答案当且仅当两个点能用首尾都在块内的边联通，并查集维护即可。

还有更好的办法：维护每个点的块内最浅祖先，比较是否相同即可。

复杂度为 。