关于树剖的小问题

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

tai_chi @ 2023-08-28 10:24:26

路径更新和查询的时候，跳链顶是选择链顶深度更大的跳，为什么不直接选择当前节点深度更大的跳？

实测后者会 WA，求解释原因。

void pathadd(int x, int y, int z)
{
    while (top[x] != top[y])
    {
        // if (dep[x] < dep[y]) 是错的
        if (dep[top[x]] < dep[top[y]])
            swap(x, y);
        add(1, dfn[top[x]], dfn[x], z);
        x = fa[top[x]];
    }
    if (dfn[x] > dfn[y])
        swap(x, y);
    add(1, dfn[x], dfn[y], z);
}

by After_light @ 2023-08-28 10:26:23

@New_Beginning 如果一下子跳到比lca更小的节点不久寄了

by After_light @ 2023-08-28 10:26:53

@After_light 如果你那条链全是重儿子，肯定不能直接往链顶跳

by After_light @ 2023-08-28 10:27:35

@New_Beginning 但是向链顶深度更大的跳是一定能保证最后跳出来lca的

by 035966_L3 @ 2023-08-28 10:27:46

@New_Beginning

比如这个，LCA(3, 5) 是 2，你求的是 1……

1 2
2 3
2 4
4 5

by tai_chi @ 2023-08-28 10:31:21

@035966_L3 但是这个样例跳到 2 的时候就已经在同一个链上了吧

by tai_chi @ 2023-08-28 10:32:18

@New_Beginning 哦不我 sb 了，是这样的

by tai_chi @ 2023-08-28 10:33:54

@After_light 就是说深度更大也可能跳的更多而错过 lca 对吧

by After_light @ 2023-08-28 15:59:08

@New_Beginning 嗯嗯

|