关于树剖的一个小问题

P3384 【模板】重链剖分/树链剖分

Albert_Wei @ 2023-06-08 17:05:05

请问为什么是判断 

depth[top[u]] < depth[top[v]]

而不是

depth[u] < depth[v]

呢？

by reveal @ 2023-06-08 17:09:27

1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
3 10

显然 1\to 9 与 10 为两条重链，求 9 与 10 的 LCA 时如果跳 9 则 LCA 为 1

by yizhiming @ 2023-06-08 17:10:28

@Albert_Wei 因为这个操作是防止 u 跳到 LCA 上方的，易证每次跳链顶深度大的那个点一定不会跳出去

by Albert_Wei @ 2023-06-08 17:10:51

@reveal thx，那请问

depth[top[u]] < depth[top[v]]

怎么证明是正确的？

by Albert_Wei @ 2023-06-08 17:12:59

@yizhiming thx，此贴结

|