xiaoMa
"Bye Bye Baby Blue"
P3384,HAOI2015(树链剖分)

树剖代码量还是很大的,如果没有压行的话,200+是肯定要的😁。

感觉我的手速跟不上了。。。

P3348 题目描述

如题,已知一棵包含 $N$个结点的树(连通且无环),每个节点上包含一个数值,需要支持以下操作:

  • 操作 $1$: 格式: $1$ $x$ $y$ $z$表示将树从 $x$ 到 $y$结点最短路径上所有节点的值都加上 $z$。
  • 操作 $2$: 格式: $2$ $x$ $y$  表示求树从 $x$ 到 $y$ 结点最短路径上所有节点的值之和。
  • 操作 $3$: 格式: $3$ $x$ $z$ 表示将以$x$ 为根节点的子树内所有节点值都加上 $z$。
  • 操作 $4$: 格式: $4$  $x$  表示求以 $x$  为根节点的子树内所有节点值之和

还是求子树节点权值之和和路径节点权值和

时间复杂度

1.将树从$x$到$y$结点最短路径上所有节点的值都加上$z$,树上差分可以以$O(n+m)$的优秀复杂度解决这个问题。

2. 求树从$x$到$y$结点最短路径上所有节点的值之和 ,可以用$O(n)$处理出每个点的$dfs$,根据倍增的思想可以求出$distance(x,y)=dis[x]+dis[y]- dis[lca(x,y)] $,且复杂度是$O(n\log_2n)$。所以$LCA$复杂度是$O(m\log_2n+n)$

性质$1:$
如果边$(u,v)$,为轻边,那么$size(v)<=size(\frac{u}{2})$。
证明:显然,否则该边会成为重边
性质$2:$
树中任意两个节点之间的路径中轻边的条数不会超过 $O\log_2n$ ,重路径的数目不会超过 $O\log_2n$

有了上面两条性质,我们就可以来分析时间复杂度了
由于重路径的数量的上界为 $O\log_2n$ ,
线段树中查询/修改的复杂度为 $O\log_2n$
那么总的复杂度就是 $O(\log_2n)^2$ ,对于多次查询来说,复杂度还是可以的。

相对于多次查询来说,树上倍增LCA $O(m\log_2(n+m))$的复杂度显然不如树剖的 $O(\log_2n)^2$

/** 
 * TREE_CHAIN_SPLIT_P3384_3_CPP
 * @author : MaWeiTao 
 */
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <climits>
#include <queue>
#include <vector>
#include <stack>
#include <algorithm>
#include <cctype>


#define FAST_IO std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define sca(a) scanf("%d",&amp;a);
#define sca2(a, b) scanf("%d%d",&amp;a,&amp;b)
#define sca3(a, b, c) scanf("%d%d%d",&amp;a,&amp;b,&amp;c)
#define scac(a) scanf("%c",a);
#define scacc(a, b) scanf("%c%c",a,b)
#define mem(a, b) memset(a,b,sizeof(a))
#define Rint register int
using namespace std;
template<class T>void tomax(T &amp;a, T b) { a = max(a, b); }
template<class T>void tomin(T &amp;a, T b) { a = min(a, b); }

typedef long long ll;
typedef pair<int, int> pii;


template<typename T> inline void read(T &amp;x){
    x=0;T w=1,ch=getchar();
    while(!isdigit(ch)&amp;&amp;ch!='-')ch=getchar();
    if(ch=='-')w=-1,ch=getchar();
    while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^'0'),ch=getchar();
    x=x*w;
}


const int maxn=2e5+10;
int n,m,r,mod;
int tot,head[maxn],w[maxn],wt[maxn];
int a[maxn<<2],laz[maxn<<2];
int son[maxn],id[maxn],fa[maxn],cnt,dep[maxn],siz[maxn],top[maxn];
int res=0;

struct Edge{
    int to,next;
}e[maxn<<1];
namespace SEG{
#define mid ((l+r)>>1)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define len (r-l+1)
    inline void add(int x,int y){//链式前向星加边
        e[++tot].to=y;
        e[tot].next=head[x];
        head[x]=tot;
    }
    inline void pushup(int rt){a[rt]=(a[rt<<1]+a[rt<<1|1])%mod;}
    inline void pushdown(int rt,int lenn){
        laz[rt<<1]+=laz[rt],laz[rt<<1|1]+=laz[rt];
        a[rt<<1]+=laz[rt]*(lenn-(lenn>>1)),a[rt<<1|1]+=laz[rt]*(lenn>>1);
        a[rt<<1]%=mod,a[rt<<1|1]%=mod;
        laz[rt]=0;
    }
    inline void build(int rt,int l,int r){
        if(l==r){
            a[rt]=wt[l];
            if(a[rt]>mod)a[rt]%=mod;
            return;
        }
        build(lson),build(rson);
        pushup(rt);
    }

    inline void query(int rt,int l,int r,int x,int y){
        if(x<=l&amp;&amp;r<=y){res+=a[rt];res%=mod;return;}
        else{
            if(laz[rt])pushdown(rt,len);
            if(x<=mid)query(lson,x,y);
            if(y>mid)query(rson,x,y);
        }
    }

    inline void update(int rt,int l,int r,int L,int R,int k){
        if(L<=l&amp;&amp;r<=R){ laz[rt]+=k;a[rt]+=k*len;}
        else{
            if(laz[rt])pushdown(rt,len);
            if(L<=mid)update(lson,L,R,k);
            if(R>mid)update(rson,L,R,k);
            a[rt]=(a[rt<<1]+a[rt<<1|1])%mod;
        }
    }
}
using namespace SEG;
namespace TREE_CHAIN{
    inline int query_path(int x,int y){
        int ans=0;
        while(top[x]!=top[y]){
            if(dep[top[x]]<dep[top[y]])swap(x,y);
            res=0;
            query(1,1,n,id[top[x]],id[x]);
            ans+=res;
            ans%=mod;
            x=fa[top[x]];
        }
        if(dep[x]>dep[y])swap(x,y);
        res=0;
        query(1,1,n,id[x],id[y]);
        ans+=res;
        return ans%mod;
    }

    inline void update_path(int x,int y,int k){
        k%=mod;
        while(top[x]!=top[y]){
            if(dep[top[x]]<dep[top[y]])swap(x,y);
            update(1,1,n,id[top[x]],id[x],k);
            x=fa[top[x]];
        }
        if(dep[x]>dep[y])swap(x,y);
        update(1,1,n,id[x],id[y],k);
    }

    inline int query_son(int x){res=0;query(1,1,n,id[x],id[x]+siz[x]-1);return res;}
    inline void update_Son(int x,int k){update(1,1,n,id[x],id[x]+siz[x]-1,k);}
    inline void dfs1(int x,int f,int deep){
        dep[x]=deep;
        fa[x]=f;
        siz[x]=1;
        int maxson=-1;
        for(Rint i=head[x];i;i=e[i].next){
            int y=e[i].to;
            if(y==f)continue;
            dfs1(y,x,deep+1);
            siz[x]+=siz[y];
            if(siz[y]>maxson)son[x]=y,maxson=siz[y];
        }
    }

    inline void dfs2(int x,int tp){
        id[x]=++cnt;
        wt[cnt]=w[x];
        top[x]=tp;
        if(!son[x])return;
        dfs2(son[x],tp);
        for(Rint i=head[x];i;i=e[i].next){
            int y=e[i].to;
            if(y==fa[x]||y==son[x])continue;
            dfs2(y,y);
        }
    }
}
using namespace TREE_CHAIN;

signed main(){
    read(n);read(m);read(r);read(mod);
    for(Rint i=1;i<=n;i++)read(w[i]);
    for(Rint i=1;i<n;i++){
        int a,b;
        read(a);read(b);
        add(a,b);add(b,a);
    }
    dfs1(r,0,1),dfs2(r,r);
    build(1,1,n);
    while(m--){
        int k,x,y,z;
        read(k);
        if(k==1){read(x);read(y);read(z);update_path(x,y,z);}
        else if(k==2){read(x);read(y);printf("%d\n",query_path(x,y));}
        else if(k==3){read(x);read(y);update_Son(x,y);}
        else{read(x);printf("%d\n",query_son(x));}
    }
}

HAOI2015题目描述

有一棵点数为 $N$ 的树,以点 $1$ 为根,且树点有边权。然后有 $M$ 个操作,分为三种:

  • 操作 $1$ :把某个节点 $x$ 的点权增加 $a $。
  • 操作 $2$ :把某个节点 $x$ 为根的子树中所有点的点权都增加 $a$ 。
  • 操作 $3$ :询问某个节点 $x$ 到根的路径中所有点的点权和。
/** 
 * TREE_CHAIN_SPLIT_HAOI2015_CPP
 * @author : MaWeiTao 
 *
 */

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <climits>
#include <queue>
#include <vector>
#include <stack>
#include <algorithm>
#include <cctype>

#define FAST_IO std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define sca(a) scanf("%d",&amp;a);
#define sca2(a, b) scanf("%d%d",&amp;a,&amp;b)
#define sca3(a, b, c) scanf("%d%d%d",&amp;a,&amp;b,&amp;c)
#define scac(a) scanf("%c",a);
#define scacc(a, b) scanf("%c%c",a,b)
#define mem(a, b) memset(a,b,sizeof(a))
#define Rint register int
using namespace std;
template<class T>void tomax(T &amp;a, T b) { a = max(a, b); }
template<class T>void tomin(T &amp;a, T b) { a = min(a, b); }

typedef long long LL;
typedef pair<int, int> pii;

template<typename T> inline void read(T &amp;x){
    x=0;T w=1,ch=getchar();
    while(!isdigit(ch)&amp;&amp;ch!='-')ch=getchar();
    if(ch=='-')w=-1,ch=getchar();
    while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^'0'),ch=getchar();
    x=x*w;
}

const int maxn=1e5+10,maxm=2e5+10;
int n,m;
int tot,head[maxn];
LL w[maxn],wt[maxn];
LL a[maxn<<2],laz[maxn<<2];
int top[maxn],son[maxn],siz[maxn],id[maxn],dep[maxn],fa[maxn],cnt;
LL res=0;
struct Edge{
    int to,next;
}e[maxn<<1];
namespace SEG{
#define mid ((l+r)>>1)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define len (r-l+1)
    inline void pushup(int rt){
        a[rt]=a[rt<<1]+a[rt<<1|1];
    }
    inline void pushdown(int rt,int lenn){
        int L=(rt<<1),R=(rt<<1|1);
        LL k=laz[rt];
        a[L]+=k*(LL)(lenn-(lenn>>1)),a[R]+=k*(LL)(lenn>>1);
        laz[L]+=k,laz[R]+=k;
        laz[rt]=0;
    }
    inline void build(int rt,int l,int r){
        if(l==r){a[rt]=wt[l];return;}
        build(lson),build(rson);
        pushup(rt);
    }
    inline void query(int rt,int l,int r,int x,int y){
        if(x<=l&amp;&amp;r<=y){res+=a[rt];return;}
        if(laz[rt])pushdown(rt,len);
        if(x<=mid)query(lson,x,y);
        if(y>mid)query(rson,x,y);
    }
    inline void update(int rt,int l,int r,int x,int y,LL k){
        if(x<=l&amp;&amp;r<=y){a[rt]+=k*(LL)len;laz[rt]+=k;return;}
        if(laz[rt])pushdown(rt,len);
        if(x<=mid)update(lson,x,y,k);
        if(y>mid)update(rson,x,y,k);
        a[rt]=a[rt<<1]+a[rt<<1|1];
    }
}
using namespace SEG;
namespace TREE_CHAIN{
    inline void add(int x,int y){
        e[++tot].to=y;
        e[tot].next=head[x];
        head[x]=tot;
    }
    inline void dfs1(int x,int f,int deep){
        fa[x]=f;
        dep[x]=deep;
        siz[x]=1;
        LL maxson=-1;
        for(Rint i=head[x];i;i=e[i].next){
            int y=e[i].to;
            if(y==f)continue;
            dfs1(y,x,deep+1);
            siz[x]+=siz[y];
            if(siz[y]>maxson)son[x]=y,maxson=siz[y];
        }
    }
    inline void dfs2(int x,int tp){
        top[x]=tp;
        id[x]=++cnt;
        wt[cnt]=w[x];
        if(son[x])dfs2(son[x],tp);
        for(Rint i=head[x];i;i=e[i].next){
            int y=e[i].to;
            if(y==fa[x]||y==son[x])continue;
            dfs2(y,y);
        }
    }
    inline LL query_path(int x,int y){
        LL ans=0LL;
        while(top[x]!=top[y]){
            if(dep[top[x]]<dep[top[y]])swap(x,y);
            res=0;
            query(1,1,n,id[top[x]],id[x]);
            ans+=res;
            x=fa[top[x]];
        }
        if(dep[x]>dep[y])swap(x,y);
        res=0;
        query(1,1,n,id[x],id[y]);
        ans+=res;
        return ans;
    }
}
using namespace TREE_CHAIN;

signed main(){
    read(n);read(m);
    for(Rint i=1;i<=n;i++)read(w[i]);
    for(Rint i=1;i<n;i++){
        int a,b;
        read(a);read(b);
        add(a,b);add(b,a);
    }
    dfs1(1,0,1),dfs2(1,1);
    build(1,1,n);
    while(m--){
        int opt;read(opt);
        if(opt==1){
            int x;LL k;
            read(x);read(k);
            update(1,1,n,id[x],id[x],k);
        }
        else if(opt==2){
            int x;LL k;
            read(x);read(k);
            update(1,1,n,id[x],id[x]+siz[x]-1,k);
        }
        else{
            int x;read(x);
            printf("%lld\n",query_path(1,x));
        }
    }
}

发表评论

textsms
account_circle
email

P3384,HAOI2015(树链剖分)
树剖代码量还是很大的,如果没有压行的话,200+是肯定要的😁。感觉我的手速跟不上了。。。 P3348 题目描述 如题,已知一棵包含 $N$个结点的树(连通且无环),每个节点上包含…
扫描二维码继续阅读
2020-03-14