跳转至

树链剖分

重链剖分

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
namespace HPD
{
    int fa[MAX],siz[MAX],son[MAX],dep[MAX],dfn[MAX],rid[MAX],top[MAX],tot;
    void dfs1(int now,int father,int depth)
    {
        fa[now]=father,dep[now]=depth,siz[now]=1;
        for(auto to:G[now]) if(to!=father)
        {
            dfs1(to,now,depth+1);
            siz[now]+=siz[to];
            if(siz[to]>siz[son[now]]) son[now]=to;
        }
    }
    void dfs2(int now,int topf)
    {
        top[now]=topf,dfn[now]=++tot,rid[tot]=now;
        if(!son[now]) return;
        dfs2(son[now],topf);
        for(auto to:G[now]) if(to!=fa[now]&&to!=son[now]) dfs2(to,to); 
    }
    inline int LCA(int a,int b)
    {
        while(top[a]!=top[b])
        {
            if(dep[top[a]]<dep[top[b]]) swap(a,b);
            a=fa[top[a]];
        }
        return dep[a]<dep[b]?a:b;
    }
}