同问
by Xqbk @ 2021-04-28 20:08:22
改好了
```cpp
inline void change(int x, int y,LL k)
{
while (top[x] != top[y])
{
if (dep[x] < dep[y]) { swap(x, y); }
update(1, id[top[x]], id[x], k);
x = fa[top[x]];
}
if (dep[x] > dep[y]) { swap(x, y); }
update(1, id[x], id[y], k);
}
```
中
```cpp
if (dep[x] < dep[y]) { swap(x, y); }
```
改成
```cpp
if (dep[top[x]] < dep[top[y]]) { swap(x, y); }
```
就过了。
原因是不断向上找LCA的时候因为同一条重链是直接跳转的，所以要关注每一条链的链顶深度，将链顶更深的往上跳，才能最终相遇。
by FlaWww @ 2021-05-13 18:12:10