树链剖分 — Luogu P3384 [模板] 树链剖分

发布者：woshiluo 树链剖分 — Luogu P3384 [模板] 树链剖分有1条评论

线段树秒天秒地

0x00 写在前头

什么是树？
一种结构关系清晰，父子关系明确的数据结构
什么是树链剖分？
将一棵树分成好几条链子便于处理和用数据结构各种操作 还能便于出题人耍流氓
我需要什么？
你需要一个脑子，一双手，一个能正常上网电脑，一个编译环境，并且需要你脑子里装着一个线段树
说正常点!
你需要会线段树，或者别的什么比线段树高效的 RMQ 解决方案都行

0x01 基本概念

我们知道，在对于一棵树进行区间更新的时候，往往很多更新的节点是没有用上的，如果往下更新会进行没有用的运算，而且树上算法普遍较为复杂，难以优化，所以我们需要将树形结构变的比较容易处理 那么，先上概念
  • 重儿子: 一个节点的所有叶子节点中叶子节点最多的一个被称为这个节点的重儿子
  • 轻儿子: 在叶子节点重，它不是重儿子就只能轻儿子
  • 重边: 链接任意两个重儿子的边叫做重边
  • 轻边: 不是重边它就是轻边了
  • 重链: 相邻重边连起来的连接一条重儿子的链叫重链
  • 重链显然由轻儿子做起点
那么首先，我们先要把这些重链找出来

0x02 剖分部分

很明显，我们要找重链，首先需要找到每个节点的儿子数量和他的重儿子，在这个过程重我们可以顺便做点别的 所以我们第一次搜索是要把这些东西解决掉:
  • 每个节点的儿子数
  • 每个节点的重儿子
  • 每个节点的深度
  • 每个节点的父亲
看起来好像很简单的样子？ 上代码: 
int son[110000],mson[110000],fa[110000],dep[110000];
// son[] 节点 x 有 son[x] 个儿子
// mson[] 节点 x 的重儿子是 mson[x]
// fa[] 节点 x 的父亲是 fa[x]
// dep[] 节点 x 的深度是 dep[x]
void pre_son(int now,int la,int deep){// now - 当前节点 la - 父亲 deep - 当前深度
    int f=0,max=-1;
    fa[now]=la;
    dep[now]=deep;
    for(int i=ehead[now];i;i=e[i].next){// 标准遍历
        if(e[i].to==la) continue;// 不能遍历回去了
        pre_son(e[i].to,now,deep+1);
        f+=son[e[i].to]+1;// 加上它的儿子数和它本身
        if(son[e[i].to]>max) {max=son[e[i].to];mson[now]=e[i].to;}// 寻找重儿子
    }
    son[now]=f;// 保存叶子节点数量
}
接下来我们就要包这些节点分成链子了，为了方便处理，我们需要按照遍历顺序给每个点重新编号，并且存下来每个节点的链子的起始节点 我们的遍历顺序是重儿子优先 在这次遍历我们将要处理:
  • 每个节点所在的链子的起始节点
  • 每个节点所在的按遍历顺序的新编号
  • 将权值对应到每个新编号上
上代码吧: 
int top[110000],num[110000],val[110000],ucnt;
// top[] 点 x 所在的链子的起始节点是 top[x]
// num[] 点 x 的新编号是now[x]
// val[] 点 x 的权值是 val[ num[x] ]
void dfs(int now,int la){
    num[now]=++ucnt;// 按顺序遍历
    val[ucnt]=tval[now];// 新权值
    if(top[now]==0) top[now]=now; // 自己是轻儿子就起一条链子
    if(son[now]==0) return ;// 没有儿子就可以回去了
    top[mson[now]]=top[now];// 先遍历重儿子
    dfs(mson[now],now);
    for(int i=ehead[now];i;i=e[i].next){// 标准遍历
        if(e[i].to==la||e[i].to==mson[now]) continue;
        dfs(e[i].to,now);
    }
}

0x03 最短路查询

题目中前两种操作都要求根据在最短路上操作，那么我们该怎么求这个东西呢？ 我们之前是不是把一棵树变成了一堆链子？ 而且根据我们遍历顺序优先的原则，同一条链子上的点的序号一定是连续的 而且如果两个点在同一条链子上，那么他们之间的序号也一定是连续的 所以我们只需要循环向上，知道处于同一个链子为止 不过问题在于，怎么让他们在同一条链子上.. 如果两个点不在一条链子上的话，把其所在的链子和统计下来，然后把这个点改为这个点所在链子的起始点的父亲，最后加起来就行 那么虽然说是连续的，不过修改怎么办…
你为什么不试试万能的线段树大法呢？
当然是用线段树上去干啊 所以我们这些操作就被愉快的解决了，上代码: 
inline void change1(int from,int to,int val){
    while(top[from]!=top[to]){
        if(dep[top[to]]>dep[top[from]]){// 优先处理深的
            int tmp=to;
            to=from;
            from=tmp;
        }
        query_lazy(1,1,n,num[top[from]],num[from],val);// 先更新在继续向上
        from=fa[top[from]];
    }
    if(dep[to]<dep[from]){// 同一条链子了
        int tmp=to;
        to=from;
        from=tmp;
    }
    query_lazy(1,1,n,num[from],num[to],val);
}
// 同上
inline int change2(int from,int to){
    int ans=0;
    while(top[from]!=top[to]){
        if(dep[top[to]]>dep[top[from]]){
            int tmp=to;
            to=from;
            from=tmp;
        }
        ans=(ans+query_add(1,1,n,num[top[from]],num[from]))%p;
        from=fa[top[from]];
    }
    if(dep[to]<dep[from]){
        int tmp=to;
        to=from;
        from=tmp;
    }
    ans=(ans+query_add(1,1,n,num[from],num[to]))%p;
    return ans;
}

0x04 子树查找

很明显，子树里的序号是连续的所以我们只需要查询线段和就行了qwq

0x05 代码

#include <cstdio>
using namespace std;
int n,m,r,p,u,v,op,a,b,c;
int tval[110000];
// edge start
struct edge{
    int next,to;
}e[210000];
int ehead[110000],ecnt;
inline void add_edge(int now,int to){
    ecnt++;
    e[ecnt].to=to;
    //e[ecnt].val=val;
    e[ecnt].next=ehead[now];
    ehead[now]=ecnt;
}
// edge end
// pre son start
int son[110000],mson[110000],fa[110000],dep[110000];
void pre_son(int now,int la,int deep){
    int f=0,max=-1;
    fa[now]=la;
    dep[now]=deep;
    for(int i=ehead[now];i;i=e[i].next){
        if(e[i].to==la) continue;
        pre_son(e[i].to,now,deep+1);
        f+=son[e[i].to]+1;
        if(son[e[i].to]>max) {max=son[e[i].to];mson[now]=e[i].to;}
    }
    son[now]=f;
}
// pre son end
// dfs start
int top[110000],num[110000],val[110000],ucnt;
void dfs(int now,int la){
    num[now]=++ucnt;
    val[ucnt]=tval[now];
    if(top[now]==0) top[now]=now;
    if(son[now]==0) return ;
    top[mson[now]]=top[now];
    dfs(mson[now],now);
    for(int i=ehead[now];i;i=e[i].next){
        if(e[i].to==la||e[i].to==mson[now]) continue;
        dfs(e[i].to,now);
    }
}
// dfs end
// tree start
int tree[410000],lazy[410000];
inline void pushup(int now){
    tree[now]=(tree[now<<1]+tree[now<<1|1])%p;
}
inline void pushdown(int now,int lnum,int rnum){
    if(lazy[now]){
        lazy[now<<1]+=lazy[now];
        lazy[now<<1|1]+=lazy[now];
        tree[now<<1]+=lazy[now]*lnum;
        tree[now<<1|1]+=lazy[now]*rnum;
        lazy[now]=0;
    }
}
void build_tree(int now,int left,int rig){
    if(left==rig){tree[now]=val[rig]%p;return ;}
    build_tree(now<<1,left,(left+rig)>>1);
    build_tree((now<<1)|1,((left+rig)>>1)+1,rig);
    pushup(now);
}
void query_lazy(int now,int left,int rig,int from,int to,int val){
    if(left>=from&&rig<=to){
        tree[now]=(tree[now]+val*(rig-left+1))%p;
        lazy[now]=(lazy[now]+val)%p;
        return ;
    }
    int mid=(left+rig)>>1;
    pushdown(now,mid-left+1,rig-mid);
    if(from<=mid) query_lazy(now<<1,left,mid,from,to,val);
    if(to>mid) query_lazy(now<<1|1,mid+1,rig,from,to,val);
    pushup(now);
}
int query_add(int now,int left,int rig,int from,int to){
    if(left>=from&&rig<=to){
        return tree[now]%p;
    }
    int mid=(left+rig)>>1;
    int res=0;
    pushdown(now,mid-left+1,rig-mid);
    if(from<=mid) res+=query_add(now<<1,left,mid,from,to);
    if(to>mid) res+=query_add(now<<1|1,mid+1,rig,from,to);
    return res%p;
}
// tree end
// important start
inline void change1(int from,int to,int val){
    while(top[from]!=top[to]){
        if(dep[top[to]]>dep[top[from]]){
            int tmp=to;
            to=from;
            from=tmp;
        }
        query_lazy(1,1,n,num[top[from]],num[from],val);
        from=fa[top[from]];
    }
    if(dep[to]<dep[from]){
        int tmp=to;
        to=from;
        from=tmp;
    }
    query_lazy(1,1,n,num[from],num[to],val);
}
inline int change2(int from,int to){
    int ans=0;
    while(top[from]!=top[to]){
        if(dep[top[to]]>dep[top[from]]){
            int tmp=to;
            to=from;
            from=tmp;
        }
        ans=(ans+query_add(1,1,n,num[top[from]],num[from]))%p;
        from=fa[top[from]];
    }
    if(dep[to]<dep[from]){
        int tmp=to;
        to=from;
        from=tmp;
    }
    ans=(ans+query_add(1,1,n,num[from],num[to]))%p;
    return ans;
}
inline void change3(int now,int val){
    query_lazy(1,1,n,num[now],num[now]+son[now],val);
}
inline int change4(int now){
    return query_add(1,1,n,num[now],num[now]+son[now]);
}
void print_tree(int now,int left,int rig){
    if(left==rig){printf("%d ",tree[now]);return ;}
    int mid=(left+rig)>>1;
    pushdown(now,mid-left+1,rig-mid);
    print_tree(now<<1,left,(left+rig)>>1);
    print_tree((now<<1)|1,((left+rig)>>1)+1,rig);
}
int main(){
    //freopen("luogu.3384.out","w",stdout);
    scanf("%d%d%d%d",&n,&m,&r,&p);
    for(int i=1;i<=n;i++) scanf("%d",&tval[i]);
    for(int i=1;i<n;i++){
        scanf("%d%d",&u,&v);
        add_edge(u,v);
        add_edge(v,u);
    }
    pre_son(r,0,0);
    dfs(r,0);
    fa[r]=r;
    build_tree(1,1,n);
    for(int i=1;i<=m;i++){
        scanf("%d",&op);
        if(op==1){
            scanf("%d%d%d",&a,&b,&c);
            change1(a,b,c);
        }
        if(op==2){
            scanf("%d%d",&a,&b);
            printf("%d\n",change2(a,b)%p);
        }
        if(op==3){
            scanf("%d%d",&a,&b);
            change3(a,b);
        }
        if(op==4){
            scanf("%d",&a);
            printf("%d\n",change4(a)%p);
        }
        //print_tree(1,1,n);
        //printf("\n");
    }
}
// important end

End

]]>

加入对话

1条评论

  1. Pingback： [SDOI2011]染色 — 树链剖分 – Woshiluo's Notebook
留下评论

电子邮件地址不会被公开。 必填项已用*标注