重鏈剖分

思想

我先給出一些定義:

定義一個結點的重子節點為其子節點中子樹節點數最大的子節點，如有多個，隨便取一個作為重兒子，如果沒有子節點，就沒有重兒子。

定義一個結點的輕子節點為其除重子節點外的子節點。

從這個節點到重子節點的邊為重邊，到其他子節點的邊為輕邊。

由重邊首位相連的鏈稱為重鏈。

把落單的結點也當作重鏈，那么整棵樹就被剖分成若干條重鏈，可以證明，樹上每條路徑最多會被分成 \(O(\log{n})\) 條重鏈。

如圖：

預處理

樹剖的預處理分為兩步。

我們先給出一些定義：

\(fa(u)\) 表示節點 \(u\) 的父節點
\(dep(u)\) 表示節點 \(u\) 的深度
\(siz(u)\) 表示節點 \(u\) 的子樹結點個數
\(son(u)\) 表示節點 \(u\) 的重兒子
\(top(u)\) 表示節點 \(u\) 所在重鏈的頂部節點（深度最?。?/li>
\(dfn(u)\) 表示節點 \(u\) 的 \(dfs\) 序，也是其在線段樹中的編號
\(rnk(x)\) 表示 \(dfs\) 序所對應的節點編號，有 \(rnk(dfn(u))=u\)

我們進行兩遍 \(dfs\) 預處理這些值，第一遍預處理出 \(fa\)，\(son\)，\(siz\)，\(dep\) ，第二遍預處理出 \(top\)，\(dfn\)，\(rnk\)。

void dfs1(int u){
    son[u]=-1;
    siz[u]=1;
    for(int i=head[u];i;i=g[i].nxt){
        int v=g[i].to;
        if(!dep[v]){
            dep[v]=dep[u]+1;
            fa[v]=u;
            dfs1(v);
            siz[u]+=siz[v];
            if(son[u]==-1||siz[v]>siz[son[u]]){
                son[u]=v;
            }
        }
    }
    return;
}
int cnt=0;
void dfs2(int u,int t){
    top[u]=t;
    cnt++;
    dfn[u]=cnt;
    rnk[cnt]=u;
    if(son[u]==-1)return;
    dfs2(son[u],t);//先訪問重兒子使重鏈上的點dfn序連續
    for(int i=head[u];i;i=g[i].nxt){
        int v=g[i].to;
        if(v!=son[u]&&v!=fa[u]){
            dfs2(v,v);
        }
    }
    return;
}

LCA

題面

如題，給定一棵有根多叉樹，請求出指定兩個點直接最近的公共祖先。

思路

這題做法很多，什么倍增，\(RMQ\)，\(tarjan\) 之類的。今天我們來講用重鏈剖分做。其實很簡單，我們只需要讓兩個節點不斷按一條一條重鏈跳直到兩點處于一條重鏈時取深度低的即可。

代碼

#include<iostream>
#include<cstdio>
using namespace std;
struct edge{
    int to;
    int nxt;
}g[1000100];
int head[500100],tot;
void addedge(int x,int y){
    tot++;
    g[tot].to=y;
    g[tot].nxt=head[x];
    head[x]=tot;
    return;
}
int son[500010],top[500010],fa[500010],siz[500010],dep[500010],dfn[500010],rnk[500010];
void dfs1(int u){
    son[u]=-1;
    siz[u]=1;
    for(int i=head[u];i;i=g[i].nxt){
        int v=g[i].to;
        if(!dep[v]){
            dep[v]=dep[u]+1;
            fa[v]=u;
            dfs1(v);
            siz[u]+=siz[v];
            if(son[u]==-1||siz[v]>siz[son[u]]){
                son[u]=v;
            }
        }
    }
    return;
}
int cnt=0;
void dfs2(int u,int t){
    top[u]=t;
    cnt++;
    dfn[u]=cnt;
    rnk[cnt]=u;
    if(son[u]==-1)return;
    dfs2(son[u],t);
    for(int i=head[u];i;i=g[i].nxt){
        int v=g[i].to;
        if(v!=son[u]&&v!=fa[u]){
            dfs2(v,v);
        }
    }
    return;
}
inline int lca(int u,int v){
    while(top[u]!=top[v]){
        if(dep[top[u]]>dep[top[v]]){
            u=fa[top[u]];
        }else{
            v=fa[top[v]];
        }
    }
    return dep[u]>dep[v]?v:u;
}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,m,s;
    cin>>n>>m>>s;
    for(int i=1;i<n;++i){
        int x,y;
        cin>>x>>y;
        addedge(x,y);
        addedge(y,x);
    }
    dep[s]=1;
    dfs1(s);
    dfs2(s,s);
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        cout<<lca(x,y)<<"\n";
    }
    cout<<flush;
    return 0;
}

【模板】重鏈剖分/樹鏈剖分

題面

如題，已知一棵包含 \(N\) 個結點的樹（連通且無環），每個節點上包含一個數值，需要支持以下操作：

1 x y z，表示將樹從 \(x\) 到 \(y\) 結點最短路徑上所有節點的值都加上 \(z\)。
2 x y，表示求樹從 \(x\) 到 \(y\) 結點最短路徑上所有節點的值之和。
3 x z，表示將以 \(x\) 為根節點的子樹內所有節點值都加上 \(z\)。
4 x 表示求以 \(x\) 為根節點的子樹內所有節點值之和

思路

我們先說路徑的修改查詢，其實很簡單，我們可以像跑 \(LCA\) 一樣遍歷 \(x\) 到 \(y\) 的路徑上的每條重鏈，由于前面我們預處理時已經保證了一條重鏈的 \(dfn\) 序連續，我們可以將每個點用其 \(dfn\) 序表示，再維護一個 \(nw\) 數組用來存對應 \(dfn\) 序的初始值，用線段樹進行區間修改，區間查詢即可。再說子樹修改查詢，這個更簡單，由于子樹 \(dfn\) 序連續，直接用線段樹修改查詢即可。

代碼

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
struct edge{
    int to;
    int nxt;
}g[1000100];
int head[500100],tot;
int n,m,r,p;
inline void addedge(int x,int y){
    tot++;
    g[tot].to=y;
    g[tot].nxt=head[x];
    head[x]=tot;
    return;
}
ll a[100010];
int son[100010],top[100010],fa[100010],siz[100010],dep[100010],dfn[100010];
ll nw[100010];
void dfs1(int u){
    son[u]=-1;
    siz[u]=1;
    for(int i=head[u];i;i=g[i].nxt){
        int v=g[i].to;
        if(!dep[v]){
            dep[v]=dep[u]+1;
            fa[v]=u;
            dfs1(v);
            siz[u]+=siz[v];
            if(son[u]==-1||siz[v]>siz[son[u]]){
                son[u]=v;
            }
        }
    }
    return;
}
int cnt=0;
void dfs2(int u,int t){
    top[u]=t;
    cnt++;
    dfn[u]=cnt;
    nw[cnt]=a[u];
    if(son[u]==-1)return;
    dfs2(son[u],t);
    for(int i=head[u];i;i=g[i].nxt){
        int v=g[i].to;
        if(v!=son[u]&&v!=fa[u]){
            dfs2(v,v);
        }
    }
    return;
}
struct node{
    ll tag;
    ll val;
    ll l;
    ll r;
}tree[400100];
inline void maketag(int u,ll k){
    tree[u].val+=k*(tree[u].r-tree[u].l+1)%p;
    tree[u].val%=p;
    tree[u].tag+=k;
    return;
}
inline void pushup(int u){
    tree[u].val=(tree[u<<1].val+tree[u<<1|1].val)%p;
    return;
}
inline void pushdown(int u){
    maketag(u<<1,tree[u].tag);
    maketag(u<<1|1,tree[u].tag);
    tree[u].tag=0;
    return;
}
void build(int u,int l,int r){
    tree[u].l=l;
    tree[u].r=r;
    tree[u].tag=0;
    if(l==r){
        tree[u].val=nw[l]%p;
        return;
    }
    int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
    return;
}
void modify(int u,int l,int r,ll k){
    if(l<=tree[u].l&&tree[u].r<=r){
        maketag(u,k);
        return;
    }
    pushdown(u);
    int mid=(tree[u].l+tree[u].r)>>1;
    if(l<=mid){
        modify(u<<1,l,r,k);
    }
    if(mid<r){
        modify(u<<1|1,l,r,k);
    }
    pushup(u);
    return;
}
ll query(int u,int l,int r){
    if(l<=tree[u].l&&tree[u].r<=r){
        return tree[u].val;
    }
    pushdown(u);
    ll ans=0;
    int mid=(tree[u].l+tree[u].r)>>1;
    if(l<=mid){
        ans+=query(u<<1,l,r);
    }
    if(mid<r){
        ans+=query(u<<1|1,l,r);
    }
    return ans%p;
}
void mdfpath(int u,int v,ll k){
    k%=p;
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        modify(1,dfn[top[u]],dfn[u],k);
        u=fa[top[u]];
    }
    if(dep[u]>dep[v]){
        swap(u,v);
    }
    modify(1,dfn[u],dfn[v],k);
    return;
}
ll qrypath(int u,int v){
    ll ans=0;
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        ans+=query(1,dfn[top[u]],dfn[u]);
        ans%=p;
        u=fa[top[u]];
    }
    if(dep[u]>dep[v])swap(u,v);
    ans+=query(1,dfn[u],dfn[v]);
    ans%=p;
    return ans;
}
void mdftree(int u,int k){
    modify(1,dfn[u],dfn[u]+siz[u]-1,k%p);
    return;
}
ll qrytree(int u){
    return query(1,dfn[u],dfn[u]+siz[u]-1);
}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin>>n>>m>>r>>p;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        addedge(x,y);
        addedge(y,x);
    }
    dep[r]=1;
    dfs1(r);
    dfs2(r,r);
    build(1,1,n);
    while(m--){
        int op,x,y,z;
        cin>>op>>x;
        if(op==1){
            cin>>y>>z;
            mdfpath(x,y,z%p);
        }
        if(op==2){
            cin>>y;
            cout<<qrypath(x,y)<<"\n";
        }
        if(op==3){
            cin>>z;
            mdftree(x,z%p);
        }
        if(op==4){
            cout<<qrytree(x)<<"\n";
        }
    }
    cout<<flush;
    return 0;
}

posted @ 2024-08-25 18:54 PengDave 閱讀(76) 評論(0) 收藏舉報

刷新頁面返回頂部

pengdave

重鏈剖分

思想

預處理

LCA

題面

思路

代碼

【模板】重鏈剖分/樹鏈剖分

題面

思路

代碼

公告