虚树

 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
31
32
33
34
35
36
37
38
39
40
41
42
43
namespace VirtualTree
{
    int N,L,lca,h[MAX],stk[MAX],top;
    vector<int> G[MAX];
    struct edge{int nex,to;}e[MAX<<1];
    int head[MAX],cnt;
    inline void add(int x,int y) {e[++cnt].nex=head[x],head[x]=cnt,e[cnt].to=y;}
    int fa[MAX],son[MAX],siz[MAX],Top[MAX],dep[MAX],dfn[MAX],tot;
    void dfs1(int now,int father,int depth)
    {
        siz[now]=1,fa[now]=father,dep[now]=depth;
        for(auto to:G[now]) if(to!=father) dfs1(to,now,depth+1),siz[now]+=siz[to],son[now]=siz[to]>siz[son[now]]?to:son[now];
    }
    void dfs2(int now,int topf)
    {
        Top[now]=topf,dfn[now]=++tot;
        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 x,int y)
    {
        while(Top[x]!=Top[y]) dep[Top[x]]>dep[Top[y]]?x=fa[Top[x]]:y=fa[Top[y]];
        return dep[x]>dep[y]?y:x;
    }
    inline void build()
    {
        sort(h+1,h+N+1,[&](int a,int b){return dfn[a]<dfn[b];});
        L=h[1]; for(int i=2;i<=N;++i) L=LCA(L,h[i]);
        stk[top=1]=L,cnt=0,head[L]=0;
        for(int i=1;i<=N;++i) if(h[i]!=L)
        {
            lca=LCA(h[i],stk[top]);
            if(lca!=stk[top])
            {
                while(dfn[lca]<dfn[stk[top-1]]) add(stk[top-1],stk[top]),--top;
                if(dfn[lca]>dfn[stk[top-1]]) head[lca]=0,add(lca,stk[top]),stk[top]=lca; else add(lca,stk[top--]);
            }
            head[h[i]]=0,stk[++top]=h[i];
        }
        for(int i=1;i<top;++i) add(stk[i],stk[i+1]);
    }
}