12.2闲话-526互联

树剖树剖

调了好久的板子终于过了，主要原因是建线段树出了问题，警钟长鸣

本来应该是t[q].dat=a[T[l].rnk];

然后我打的是t[q].dat=a[l];

点击查看代码


#include<bits/stdc++.h>
#define MAXM 0X66CCFF
#define int long long
namespace IO{
    inline void close(){std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);}
    inline void Fire(){freopen(".in","r",stdin);freopen(".out","w",stdout);}
    inline int read(){int s = 0,w = 1;char ch = getchar();while(ch<'0'||ch>'9'){ if(ch == '-') w = -1;ch = getchar();}while(ch>='0'&&ch<='9'){ s = s*10+ch-'0';ch = getchar();}return s*w;}
    inline void write(int x){char F[200];int tmp=x>0?x:-x,cnt=0;;if(x<0)putchar('-') ;while(tmp>0){F[cnt++]=tmp%10+'0';tmp/=10;}while(cnt>0)putchar(F[--cnt]);}
}
using namespace IO;
int head[MAXM],NEXT[MAXM],TO[MAXM],cnt,tot,a[MAXM];
struct node{
    int fa,dep,siz,son,top;
    int dfn,rnk;
}T[MAXM];
namespace Grape{
    inline void add(int u,int v){
        NEXT[++tot]=head[u];
        TO[tot]=v;
        head[u]=tot;
    }
}
namespace ST{
    #define mid (l+r)/2
    #define lC q<<1
    #define rC q<<1|1
    struct St{
        long long l,r,siz;
        long long lazy,dat;
    }t[0x66ccff];
    void build(int q,int l,int r){
        t[q].l=l;
        t[q].r=r;
        t[q].siz=r-l+1;
        if(l==r){
            t[q].dat=a[T[l].rnk];
            return;
        }
        build(lC,l,mid);
        build(rC,mid+1,r);
        t[q].dat=t[lC].dat+t[rC].dat;
        #ifdef debug
            std::cout<<t[q].dat<<std::endl;
        #endif
    }
    void lazy(int q){
        t[lC].lazy+=t[q].lazy;
        t[lC].dat+=(t[lC].siz)*t[q].lazy;
        t[rC].lazy+=t[q].lazy;
        t[rC].dat+=(t[rC].siz)*t[q].lazy;
        t[q].lazy=0;
    }
    void change(int q,int l,int r,int v){
        if(t[q].l>r||t[q].r<l) return;
        if(t[q].l>=l && t[q].r<=r){
            t[q].lazy+=v;
            t[q].dat+=t[q].siz*v;
            return;
        }
        if(t[q].lazy!=0)
            lazy(q);
        change(lC,l,r,v);
        change(rC,l,r,v);
        t[q].dat=t[lC].dat+t[rC].dat;
    }
    long long asksum(int q,int l,int r){
        if(t[q].l>r || t[q].r<l) 
            return 0;
        if(t[q].l>=l && t[q].r<=r) 
            return t[q].dat;
        if(t[q].lazy!=0) 
            lazy(q);
        return asksum(lC,l,r)+asksum(rC,l,r); 
    }
}
namespace killTree{
    inline void Dfs1(int q){
        T[q].son=-1;
        T[q].siz=1;
        for(int j=head[q];j;j=NEXT[j]){
            if(T[TO[j]].dep) continue;
            T[TO[j]].dep=T[q].dep+1;
            T[TO[j]].fa=q;
            Dfs1(TO[j]);
            T[q].siz+=T[TO[j]].siz;
            if((T[q].son==-1) || (T[TO[j]].siz>T[T[q].son].siz)) T[q].son=TO[j];
        }
    }
    inline void Dfs2(int q,int v){
        T[q].top=v;
        T[q].dfn=++cnt;
        T[cnt].rnk=q;
        if(T[q].son==-1)
            return;
        Dfs2(T[q].son,v);
        for(int j=head[q];j;j=NEXT[j]){
            if((TO[j]!=T[q].fa)&&(TO[j]!=T[q].son))
                Dfs2(TO[j],TO[j]);
        }
    }
    inline void TreeAdd(int x,int y,int val){
        while(T[x].top!=T[y].top){
            if(T[T[x].top].dep<T[T[y].top].dep) 
                std::swap(x,y);
            ST::change(1,T[T[x].top].dfn,T[x].dfn,val);
            x=T[T[x].top].fa;
        }
        if(T[x].dep>T[y].dep) 
            std::swap(x,y);
        ST::change(1,T[x].dfn,T[y].dfn,val);
    }
    inline int TreeSum(int x,int y){
        int ans=0;
        while(T[x].top!=T[y].top){
            if(T[T[x].top].dep<T[T[y].top].dep) std::swap(x,y);
            ans=ans+ST::asksum(1,T[T[x].top].dfn,T[x].dfn);
            x=T[T[x].top].fa;
        }
        if(T[x].dep>T[y].dep) std::swap(x,y);
        return ans+ST::asksum(1,T[x].dfn,T[y].dfn);
    }
    inline void AddTree(int x,int val){
        ST::change(1,T[x].dfn,T[x].dfn+T[x].siz-1,val);
    }
    inline int AskTree(int x){
        return ST::asksum(1,T[x].dfn,T[x].dfn+T[x].siz-1);
    }
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif 
    int N=read(),M=read(),R=read();
    for(int i=1;i<=N;i++)
        a[i]=read();
    for(int i=1;i<N;i++){
        int u=read(),v=read();
        Grape::add(u,v);
        Grape::add(v,u);
    }
    T[R].dep=1;
    killTree::Dfs1(R);
    killTree::Dfs2(R,R);
    ST::build(1,1,N);
    for(int i=1;i<=M;i++){
        int q=read();
        if(q==1){
            int x=read(),y=read();
            killTree::AddTree(x,y);
        }
        else{
            int x=read();
            std::cout<<killTree::AskTree(x)<<std::endl;
        }
    }
}

B.HAOI2015 树上操作

有一棵点数为 \(N\) 的树，以点 \(1\) 为根，且树点有边权。然后有 \(M\) 个
操作，分为三种：

操作 1 ：把某个节点 \(x\) 的点权增加 \(a\) 。
操作 2 ：把某个节点 \(x\) 为根的子树中所有点的点权都增加 \(a\) 。
操作 3 ：询问某个节点 \(x\) 到根的路径中所有点的点权和。

您一眼秒了它，这不是板子吗

点击查看代码



#include<bits/stdc++.h>
#define MAXM 0X66CCFF
#define int long long
namespace IO{
    inline void close(){std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);}
    inline void Fire(){freopen(".in","r",stdin);freopen(".out","w",stdout);}
    inline int read(){int s = 0,w = 1;char ch = getchar();while(ch<'0'||ch>'9'){ if(ch == '-') w = -1;ch = getchar();}while(ch>='0'&&ch<='9'){ s = s*10+ch-'0';ch = getchar();}return s*w;}
    inline void write(int x){char F[200];int tmp=x>0?x:-x,cnt=0;;if(x<0)putchar('-') ;while(tmp>0){F[cnt++]=tmp%10+'0';tmp/=10;}while(cnt>0)putchar(F[--cnt]);}
}
using namespace IO;
int head[MAXM],NEXT[MAXM],TO[MAXM],cnt,tot,a[MAXM];
struct node{
    int fa,dep,siz,son,top;
    int dfn,rnk;
}T[MAXM];
namespace Grape{
    inline void add(int u,int v){
        NEXT[++tot]=head[u];
        TO[tot]=v;
        head[u]=tot;
    }
}
namespace ST{
    #define mid (l+r)/2
    #define lC q<<1
    #define rC q<<1|1
    struct St{
        long long l,r,siz;
        long long lazy,dat;
    }t[0x66ccff];
    void build(int q,int l,int r){
        t[q].l=l;
        t[q].r=r;
        t[q].siz=r-l+1;
        if(l==r){
            t[q].dat=a[T[l].rnk];
            return;
        }
        build(lC,l,mid);
        build(rC,mid+1,r);
        t[q].dat=t[lC].dat+t[rC].dat;
        #ifdef debug
            std::cout<<t[q].dat<<std::endl;
        #endif
    }
    void lazy(int q){
        t[lC].lazy+=t[q].lazy;
        t[lC].dat+=(t[lC].siz)*t[q].lazy;
        t[rC].lazy+=t[q].lazy;
        t[rC].dat+=(t[rC].siz)*t[q].lazy;
        t[q].lazy=0;
    }
    void change(int q,int l,int r,int v){
        if(t[q].l>r||t[q].r<l) return;
        if(t[q].l>=l && t[q].r<=r){
            t[q].lazy+=v;
            t[q].dat+=t[q].siz*v;
            return;
        }
        if(t[q].lazy!=0)
            lazy(q);
        change(lC,l,r,v);
        change(rC,l,r,v);
        t[q].dat=t[lC].dat+t[rC].dat;
    }
    long long asksum(int q,int l,int r){
        if(t[q].l>r || t[q].r<l) 
            return 0;
        if(t[q].l>=l && t[q].r<=r) 
            return t[q].dat;
        if(t[q].lazy!=0) 
            lazy(q);
        return asksum(lC,l,r)+asksum(rC,l,r); 
    }
}
namespace killTree{
    inline void Dfs1(int q){
        T[q].son=-1;
        T[q].siz=1;
        for(int j=head[q];j;j=NEXT[j]){
            if(T[TO[j]].dep) continue;
            T[TO[j]].dep=T[q].dep+1;
            T[TO[j]].fa=q;
            Dfs1(TO[j]);
            T[q].siz+=T[TO[j]].siz;
            if((T[q].son==-1) || (T[TO[j]].siz>T[T[q].son].siz)) T[q].son=TO[j];
        }
    }
    inline void Dfs2(int q,int v){
        T[q].top=v;
        T[q].dfn=++cnt;
        T[cnt].rnk=q;
        if(T[q].son==-1)
            return;
        Dfs2(T[q].son,v);
        for(int j=head[q];j;j=NEXT[j]){
            if((TO[j]!=T[q].fa)&&(TO[j]!=T[q].son))
                Dfs2(TO[j],TO[j]);
        }
    }
    inline void TreeAdd(int x,int y,int val){
        while(T[x].top!=T[y].top){
            if(T[T[x].top].dep<T[T[y].top].dep) 
                std::swap(x,y);
            ST::change(1,T[T[x].top].dfn,T[x].dfn,val);
            x=T[T[x].top].fa;
        }
        if(T[x].dep>T[y].dep) 
            std::swap(x,y);
        ST::change(1,T[x].dfn,T[y].dfn,val);
    }
    inline int TreeSum(int x,int y){
        int ans=0;
        while(T[x].top!=T[y].top){
            if(T[T[x].top].dep<T[T[y].top].dep) std::swap(x,y);
            ans=ans+ST::asksum(1,T[T[x].top].dfn,T[x].dfn);
            x=T[T[x].top].fa;
        }
        if(T[x].dep>T[y].dep) std::swap(x,y);
        return ans+ST::asksum(1,T[x].dfn,T[y].dfn);
    }
    inline void AddTree(int x,int val){
        ST::change(1,T[x].dfn,T[x].dfn+T[x].siz-1,val);
    }
    inline int AskTree(int x){
        return ST::asksum(1,T[x].dfn,T[x].dfn+T[x].siz-1);
    }
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif 
    int N=read(),M=read(),R=1;
    for(int i=1;i<=N;i++)
        a[i]=read();
    for(int i=1;i<N;i++){
        int u=read(),v=read();
        Grape::add(u,v);
        Grape::add(v,u);
    }
    T[R].dep=1;
    killTree::Dfs1(R);
    killTree::Dfs2(R,R);
    ST::build(1,1,N);
    for(int i=1;i<=M;i++){
        int q=read();
        if(q==1){
            int x=read(),y=read();
            killTree::TreeAdd(x,x,y);
        }
        else if(q==2){
            int x=read(),y=read();
            killTree::AddTree(x,y);
        }
        else{
            int x=read();
            std::cout<<killTree::TreeSum(x,R)<<std::endl;
        }
    }
}

树剖其他操作

边权转点权

众所周知，树剖都是用的点权，但是有题目用边权怎么办(~~办不了~~)

好吧其实很简单

首先想一下树的性质:除了root以外的每个点有且只有一个父节点

所以有一个简单的方法

那就是把这个节点到父节点的边权记录为这个节点的点权，然后没了

但是有个注意的点

在区间\(\{\mathrm{T[x].dfn\sim T[y].dfn}\}\)中有一个点是尊贵的\(\mathrm{LCA(x,y)}\),这个点记录的是它与它父亲相连的边的权值,不在\(x,y\)的路径上

所以在查询/修改的时候，最后的区间是 \(\{\mathrm{T[x].dfn+1,T[y].dfn}\}\)

而且要判断 \(y\) 是不是\(\mathrm{LCA(x,y)}\),若是,则无需再查询/修改了

换根操作

一般树剖会有一个固定的root，所以只需剖一次就能找到所有需要的信息。

然而换根操作会改变根节点，使本来固定的信息变化。

然而，我们肯定不能每换一个根节点就重新剖一次，~~TLE警告~~，考虑只剖一次再依靠固定的信息来进行操作

树剖是靠 dfn 把一棵树变成序列，再靠线段树/树状数组维护。我们可以用 dfn 来实现换根

首先，要知道无论怎么换根都不会让路径改变(树的特性)

假设要访问最小值\(\mathrm{Treemin(x)}\) (设当前根节点为rootnow)

分类讨论

\(\mathrm{x=rootnow}\)

直接输出整棵树的\(\min\)就行
\(\mathrm{x}\)不在\(\mathrm{rootnow}\)到原本的\(\mathrm{root}\)的路径里

这样对\(\mathrm{x}\)的子树范围不存在影响，直接查询\(\mathrm{Treemin(x)}\)
\(\mathrm{x}\)在\(\mathrm{rootnow}\)到原本的\(\mathrm{root}\)的路径里

这个是最恶心的()

\(\mathrm{x}\)的\(\mathrm{son}\)中包含\(\mathrm{rootnow}\)的（设为\(\mathrm{ch}\)) 会变成\(\mathrm{x}\)的父节点，\(\mathrm{ch}\)兄弟节点不变，仍为\(\mathrm{x}\)的子节点，

\(\mathrm{x}\)的父节点会变成\(\mathrm{x}\)的子节点，并且这个变化会从\(\mathrm{x}\)沿\(\mathrm x\)到\(\mathrm 1\)的路径，传递给路径上的每个节点。

也就是说，相当于整棵以\(\mathrm 1\)为根的树，除去以\(\mathrm{ch}\)为根的子树，都变成了查询对象。

我们考虑怎么求出\(\mathrm{ch}\)
- 考虑跳链
  
  每次让深度大的点（\(x\))向上跳，如果 \(x\) 所在的重链的起点的父节点就是深度小的点（\(y\)），直接返回 \(x\) 所在重链的起点。
  
  跳到最后，\(x\) 就变成了LCA(\(x\),\(y\))（然而因为 \(x\) 在 \(y\) 的子树中其实就是swap(\(x\),\(y\)) ）
  
  并且 \(x\) 和 \(y\) 在一条重链上，所以 \(ch\) 就是 \(x\) 的重儿子，因为只有重儿子才会和父节点在一条重链上。
  
  接下来要判断 \(ch\) 的子树的范围，如果 \(ch\) 的子树已经到了 \(n\)，就不需要查询 \(dfn[ch] + size[ch]\) 到 \(n\) 了。

centos7 centos oracle 12.2

2023 12

p12

12c