欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

树链剖分 复习笔记

程序员文章站 2024-02-14 09:50:16
...

前言

以前学树链剖分感觉好难,现在好多了,想写个笔记总结一下心得

引入

题目

洛谷P3384
树链剖分 复习笔记

思考

诶?怎么那么像线段树的题目。但是这可是在一棵树上,不是在一个数列上哦。或许可以把一棵树拆成好几个数列?

这样行么?

行,怎么不行。我们只要从树上挑去一个链,把这个链做成数列,不停循环下去直到这个树被分割完,不亦说乎?

其实我们所说的树就可以看成一个所有数列都仅为一个点的树

算法

效率最大化

那么,如何使算法效率最高?
我们想一想,如果每个数列都很短,那么,更改一个很长的链时就需要访问许多数列,耗费时间。所以要找到尽量长的链

重边

这里念“重量”的重
其他文章在这里讲得太严谨了,更难懂。在这里给一个通俗但是没那么严谨的解释

对于一个点,链接它的最重子树的边便是重边

要注意一点

如果有多个子树重量相同,则都是重边

反之,是轻边。

重链

就是连续重边连成的链。
反之叫做轻链。

建线段树

现在,把每个重链看成一条数列。
然后建线段树(或树状数组,这个看题目)

实现

古老代码,码风奇特。

#include<cstdio>
#include<algorithm>

using namespace std;

int head[100010], sum[400010], son[100010], laz[400010], w[100010], nw[100010], id[100010],  cnt, fa[100010], OYPK_cnt, deep[100010], siz[100010], top[100010];

struct EDGE{
    int y, nex;
}edge[200010];

int n, m, s, mo;

void add(int x, int y){
    edge[++OYPK_cnt].y=y;
    edge[OYPK_cnt].nex=head[x];
    head[x]=OYPK_cnt;
}

void dfs1(int x, int fat, int dep){
    deep[x]=dep;
    fa[x]=fat;
    siz[x]=1;
    int max_son=-1;
    for(int i=head[x]; i; i=edge[i].nex){
        int y=edge[i].y;
        if(y!=fat){
            dfs1(y, x, dep+1);
            if(siz[y]>max_son){
                max_son=siz[y];
                son[x]=y;
            }
            siz[x]+=siz[y];
        }
    }
}

void dfs2(int x, int hea){
    id[x]=++cnt;
    nw[cnt]=w[x];
    top[x]=hea;
    if(!son[x]){
        return;
    }
    dfs2(son[x], hea);
    for(int i=head[x]; i; i=edge[i].nex){
        int y=edge[i].y;
        if(y!=fa[x]&&y!=son[x]){
            dfs2(y, y);
        }
    }
}

void push_down(int l, int r, int rt){
    if(laz[rt]!=0){
        laz[rt<<1]+=laz[rt];
        laz[rt<<1|1]+=laz[rt];
        int mid=(l+r)>>1;
        sum[rt<<1]+=laz[rt]*(mid-l+1);
        sum[rt<<1|1]+=laz[rt]*(r-mid);
        sum[rt<<1]%=mo;
        sum[rt<<1|1]%=mo;
        laz[rt]=0;
    }
}
void build(int l, int r, int rt){
    if(l==r){
        sum[rt]=nw[l]%mo;
        return;
    }
    int mid=(l+r)>>1;
    build(l, mid, rt<<1);
    build(mid+1, r, rt<<1|1);
    sum[rt]=(sum[rt<<1]+sum[rt<<1|1])%mo;
}

int query(int a, int b, int l, int r, int rt){
    if(a<=l&&r<=b){
        return sum[rt];
    }
    push_down(l, r, rt);
    int mid=(l+r)>>1, now_ans=0;
    if(a<=mid){
        now_ans+=query(a, b, l, mid, rt<<1);
    }
    if(b>mid){
        now_ans+=query(a, b, mid+1, r, rt<<1|1);
    }
    now_ans%=mo;
    return now_ans;
}


void update(int a, int b, int l, int r, int rt, int jia){
    if(a<=l&&r<=b){
        laz[rt]+=jia;
        sum[rt]+=jia*(r-l+1);
        return;
    }
    push_down(l, r, rt);
    int mid=(l+r)>>1;
    if(a<=mid){
        update(a, b, l, mid, rt<<1, jia);
    }
    if(b>mid){
        update(a, b, mid+1, r, rt<<1|1, jia);
    }
    sum[rt]=(sum[rt<<1]+sum[rt<<1|1])%mo;
}

int q_bian(int x, int y){
    int now_ans=0;
    while(top[x]!=top[y]){
        if(deep[top[x]]<deep[top[y]]){
            swap(x, y);
        }
        now_ans+=query(id[top[x]], id[x], 1, n, 1);
        now_ans%=mo;
        x=fa[top[x]];
    }
    if(deep[x]>deep[y]){
        int t=x;
        x=y;
        y=t;
    }
    now_ans+=query(id[x], id[y], 1, n, 1);
    now_ans%=mo;
    return now_ans;
}

void up_bian(int x, int y, int jia){
    jia%=mo;
    while(top[x]!=top[y]){
        if(deep[top[x]]<deep[top[y]]){
            swap(x, y);
        }
        update(id[top[x]], id[x], 1, n, 1, jia);
        x=fa[top[x]];
    }
    if(deep[x]>deep[y]){
        swap(x, y);
    }
    update(id[x], id[y], 1, n, 1, jia);
}

int q_son(int x){
    int now_ans=query(id[x], id[x]+siz[x]-1, 1, n, 1);
    now_ans%=mo;
    return now_ans;
}

void up_son(int x, int k){
    update(id[x], id[x]+siz[x]-1, 1, n, 1, k);
}

int main(){
    //freopen("a.out", "w", stdout);
    scanf("%d%d%d%d", &n, &m, &s, &mo);
    for(int i=1; i<=n; i++){
        scanf("%d", &w[i]);
    }
    for(int i=1; i<=n-1; i++){
        int x, y;
        scanf("%d%d", &x, &y);
        add(x, y);
        add(y, x);
    }
    dfs1(s, 0, 1);
    dfs2(s, s);
    build(1, n, 1);
    for(int i=1; i<=m; i++){
        int flag;
        scanf("%d", &flag);
        if(flag==1){
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            up_bian(x, y, z);
            continue;
        }
        if(flag==2){
            int x, y;
            scanf("%d%d", &x, &y);
            printf("%d\n", q_bian(x, y));
            continue;
        }
        if(flag==3){
            int x, y;
            scanf("%d%d", &x, &y);
            up_son(x, y);
            continue;
        }
        if(flag==4){
            int x;
            scanf("%d", &x);
            printf("%d\n", q_son(x));
        }
    }
}

后记

鸣谢

洛谷(提供题目)

关于作者

初一蒟蒻,天天被大佬虐。

相关标签: 树链剖分