长链剖分

约 127 个字 120 行代码 预计阅读时间 2 分钟

类似重链剖分，不过重儿子是子节点中子树深度最大的子节点

根节点到任意节点经过的轻边最多 $\sqrt n$ 条

任意一个点的k次祖先y所在的长链的长度大于等于k

长链剖分解决，子树，深度相关，静态查询问题

dsu on tree 是所有节点共用一个答案数组，长链剖分是同一条重链共用一个答案数组

时间复杂度

$O(n)$

const int N=5e5+3;
const int M=__lg(N)+1;
namespace longPathDecomposition
{
    int n,dfsOrder;
    vector<int> e[N];
    int son[N],len[N],dep[N],fa[M][N];//siz[u]变成了u的子树高度len[u]
    int top[N],dfn[N],lasdfn[N],node[N];//lasdfn表示子树里的点最大dfs序，node[x]表示dfs序是x的点
    void addEdge(int u, int v)
    {
        e[u].push_back(v);
        e[v].push_back(u);
    }
    void dfs1(int u)
    {
        len[u]=1;
        for (int &v:e[u])
        {
            if (v == fa[0][u])
                continue;
            fa[0][v] = u;
            dep[v]=dep[u]+1;
            dfs1(v);
            if(len[v]+1<=len[u])
                continue;
            son[u]=v;
            len[u]=len[v]+1;
        }
    }
    void dfs2(int u,int tp)
    {
        dfn[u] = ++dfsOrder;
        top[u]=tp;
        node[dfsOrder]=u;
        if (son[u] == 0)
            return;
        dfs2(son[u],tp);
        for(int &v:e[u])
        {
            if (v != son[u] && v != fa[0][u])
                dfs2(v,v);
        }
        lasdfn[u]=dfsOrder;
    }
    void init(int nn)
    {
        n=nn;
        memset(son,0,sizeof(int)*(n+1));
        dfsOrder=0;
        for(int i=0;i<=n;++i)
            e[i].clear();
    }
// {
    //求k级祖先
    vector<int> anc[N], des[N];
    void initKthAnc()
    {
        //倍增处理2^i祖先
        for (int i = 1; i <= __lg(n); ++i)
            for (int j = 1; j <= n; ++j)
                fa[i][j] = fa[i - 1][fa[i - 1][j]];
        //处理链顶前后,链长个点
        for (int i = 1; i <= n; ++i)
        {
            if(top[i]!=i)
                continue;
            for(int j=0,v=i;j<len[i];++j,v=fa[0][v])
                anc[i].push_back(v);
            for (int j=0;j<len[i];++j)
                des[i].push_back(node[dfn[i]+j]);
        }
    }
    int query(int u,int k)
    {
        if(!k)
            return u;
        int i=__lg(k),v=fa[i][u],tp=top[v];
        int d=k-(1<<i)+dep[tp]-dep[v];
        if(d>0)
            return anc[tp][d];
        return des[tp][-d];
    }
// }
    void init2(int rt=1)
    {
        dep[rt]=1;
        dfs1(rt);
        dfs2(rt,rt);
        // initKthAnc();
    }
// {
    //优化DP
    int ans[N],dp[N];
    void run(int u)
    {
        if(son[u])
        {
            run(son[u]);
            //用son[u]更新u的答案
        }
        //任何地方更新u的DP，用u的dfs序做下标，这样方便轻链的信息合并到重链上
        // dp[dfn[u]]=114514;
        for(int &v:e[u])
        {
            if(v==fa[u] || v==son[u])
                continue;
            run(v);
            for(int i=dfn[v],j=dfn[u]+1;i<=lasdfn[v];++i,++j)
            {
                //轻链信息合并到重链上
                //dp[j]=merge(dp[j],dp[i]);
                //同时更新u的答案
            }
        }
    }
// }
};
init(n);
addEdge(u,v);
init2(rt);