数据结构

• 单调队列
• LCA√
• 二叉堆√
• ST表 √
• 并查集、带权并查集
• 树的直径、树的重心
• 树状数组、线段树(见线段树专题)
• 树上倍增
• 树上分治
• 哈希（整数哈希+字符哈希+树哈希）
• 树链剖分：重链剖分+长链剖分
• 启发式合并
• 平衡树(无旋Treap)

1.带权并查集

·怎样理解“带权”：即在维护点之间的集合关系时，维护的点状态的相关信息，最常见例如dep,sz....

·难点：getfather的变化

·例题：NOI2002 DAY1 T1

关键要想到怎么维护dep

//难点：
//1.sz合并的位置 
//2.dep的更新方式 
#include<bits/stdc++.h>
#define E(i,n) for(int i=1;i<=n;++i)
#define F(i,l,r) for(int i=l;i<=r;++i)
#define G(i,r,l) for(int i=r;i>=l;--i)
using namespace std;
const int N=3e4+5;
int dep[N],fa[N],sz[N],t;
inline int getfather(int x){
    if(fa[x]!=x){
        int fff=getfather(fa[x]);//先更新原来父节点的dep
        dep[x]+=dep[fa[x]];//再更新自己的dep
        fa[x]=fff;//最后来更新自己的父节点int tmp=sz[fa[x]];
    }
    return fa[x];
}
int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>t; char op[5]; int x,y; E(i,30000) fa[i]=i, sz[i]=1, dep[i]=0;
    while(t--){
        cin>>op>>x>>y;
        int fx=getfather(x),fy=getfather(y);
        if(op[0]=='M') {
            if(fx!=fy) fa[fx]=fy,dep[fx]=sz[fy],sz[fy]+=sz[fx];//注意不在getfather时维护sz而在合并时                              -1
        }
        else {
            if(fx!=fy) cout<<"-1\n";        
            else cout<<abs(dep[y]-dep[x])-1<<'\n';
        }
    }
    return 0;
}

2.树链剖分

（1）重链剖分

·树链剖分，本质就是把树上信息的维护转化成区间序列上的更新问题，转化过程其实就是把一棵树剖成很多条链，利用链上节点dfn序连续的。此过程由dfs_1,dfs_2,pathupd,pathqry实现

#include<bits/stdc++.h>
#define ls p*2
#define rs p*2+1
#define lson x,(x+y)/2,ls
#define rson (x+y)/2+1,y,rs
#define mid tr[p].l+tr[p].r>>1
#define E(i,n) for(int i=1;i<=n;++i)
#define F(i,l,r) for(int i=l;i<=r;++i)
#define G(i,r,l) for(int i=r;i>=l;--i)
using namespace std;
char buf[1<<19],*p1=buf,*p2=buf;
inline int gc(){ return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,1<<19,stdin),p1==p2)?EOF:*p1++; }
inline int rd(){
    int x=0; char ch=gc();
    while(!isdigit(ch)) ch=gc();
    while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=gc();
    return x;
}
const int N=1e5+5;
struct node{
    int v,ne;
}e[N<<1];
struct tree{
    int l,r,sum,add;
}tr[N<<2];
int w[N],n,m,rt,mod;
int first[N],k=0;
int    sz[N],son[N],dep[N],fa[N];//dfs_1
int dfn[N],cnt=0,a[N],top[N];//dfs_2
inline void add(int x,int y){ e[++k].v=y; e[k].ne=first[x]; first[x]=k; }
//------------------------线段树 
inline void pushdown(int p){
    if(tr[p].add){
        tr[ls].add=(tr[ls].add+tr[p].add)%mod; 
        tr[rs].add=(tr[rs].add+tr[p].add)%mod;
        tr[ls].sum=(tr[ls].sum+tr[p].add*(tr[ls].r-tr[ls].l+1)%mod)%mod; 
        tr[rs].sum=(tr[rs].sum+tr[p].add*(tr[rs].r-tr[rs].l+1)%mod)%mod; 
        tr[p].add=0; 
    }
}
inline void pushup(int p){ tr[p].sum=(tr[ls].sum+tr[rs].sum)%mod; }
inline void build(int x,int y,int p){
    tr[p]=(tree){ x,y,a[x],0 };
    if(x==y) return ;
    build(lson); build(rson);
    pushup(p);
}
inline void upd(int x,int y,int z,int p){
    if(tr[p].l>=x && tr[p].r<=y){
        tr[p].sum=(tr[p].sum+(tr[p].r-tr[p].l+1)*z%mod)%mod;
        tr[p].add=(tr[p].add+z)%mod;
        return ;//1.完全包含就直接return 
    } pushdown(p);
    if(mid>=x) upd(x,y,z,ls);
    if(mid<y) upd(x,y,z,rs);
    pushup(p);
}
inline int qry(int x,int y,int p){
    if(tr[p].l>=x && tr[p].r<=y) return tr[p].sum;
    pushdown(p); int res=0;
    if(mid>=x) res=(res+qry(x,y,ls))%mod;
    if(mid<y) res=(res+qry(x,y,rs))%mod;    
    return res;    
}
//----------------------------重链剖分 
inline void dfs_1(int u,int f){
    sz[u]=1; dep[u]=dep[f]+1; fa[u]=f;
    for(int i=first[u];i;i=e[i].ne){
        int v=e[i].v; if(v==f) continue;
        dfs_1(v,u);
        sz[u]+=sz[v]; 
        if(sz[son[u]]<sz[v]) son[u]=v;
    }
} 
inline void dfs_2(int u,int f,int topf){
    dfn[u]=++cnt; a[cnt]=w[u]%mod; top[u]=topf;//2.注意w[u]一放进来就要mod一下 
    if(son[u]) dfs_2(son[u],u,topf);
    for(int i=first[u];i;i=e[i].ne){
        int v=e[i].v; if(v==f || v==son[u]) continue;
        dfs_2(v,u,v);//3.轻儿子在一条以自己为链顶的链上(长度大于等于1) 
    }
}
inline void path_upd(int x,int y,int z){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        //4.比较的是链顶的高度而非x,y的高度,因为从深链顶中的点往上跳才能保证不会跳过lca(x,y) 
        upd(dfn[top[x]],dfn[x],z,1);//5.注意dfn序谁大谁小 
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    upd(dfn[x],dfn[y],z,1);
}
inline int path_qry(int x,int y){
    int res=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        res=(res+qry(dfn[top[x]],dfn[x],1))%mod;
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    res=(res+qry(dfn[x],dfn[y],1))%mod;
    return res;
}
int main(){
//    freopen("a.in","r",stdin);
//    freopen("a.out","w",stdout); 
    n=rd(),m=rd(),rt=rd(),mod=rd();
    E(i,n) w[i]=rd(); int op,x,y,z;
    E(i,n-1) x=rd(),y=rd(),add(x,y),add(y,x); 
    dfs_1(rt,0); dfs_2(rt,0,rt); build(1,n,1); 
    while(m--){
        op=rd();
        if(op==1) x=rd(),y=rd(),z=rd(),path_upd(x,y,z);
        if(op==2) x=rd(),y=rd(),printf("%d\n",path_qry(x,y));
        if(op==3) x=rd(),z=rd(),upd(dfn[x],dfn[x]+sz[x]-1,z,1);
        if(op==4) x=rd(),printf("%d\n",qry(dfn[x],dfn[x]+sz[x]-1,1));//6.操作子树的情况,注意sz[x]+1是加在外面 
    }
    return 0;
}

（2）长链剖分:优化树上DP

#include<bits/stdc++.h>
#define mid tr[p].l+tr[p].r>>1
#define E(i,n) for(int i=1;i<=n;++i)
#define F(i,l,r) for(int i=l;i<=r;++i)
#define G(i,r,l) for(int i=r;i>=l;--i)
using namespace std;
char buf[1<<19],*p1=buf,*p2=buf;
inline int gc(){ return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,1<<19,stdin),p1==p2)?EOF:*p1++; }
inline int rd(){
    int x=0; char ch=gc();
    while(!isdigit(ch)) ch=gc();
    while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=gc();
    return x;
}
const int N=1e6+5;
struct node{
    int v,ne;
}e[N<<1];
int n,Buf[N],*f[N],*p=Buf,len[N],son[N],first[N],ans[N],k=0;
//f[i][j]:离i距离为j的点的个数 
//f[]:点个数   ans[]:长度 
inline void add(int x,int y) { e[++k].v=y; e[k].ne=first[x]; first[x]=k; }
inline void dfs(int u,int fa){//长链剖分:len其实是点个数 
    len[u]=1; 
    for(int i=first[u];i;i=e[i].ne){
        int v=e[i].v; if(v==fa) continue;
        dfs(v,u); 
        if(len[v]>len[son[u]]) son[u]=v;
    }
    len[u]+=len[son[u]];
}
inline void dp(int u,int fa){
    ans[u]=0; f[u][0]=1;
    if(son[u]){//重儿子所在链直接继承 
        f[son[u]]=f[u]+1;//共享内存:所以不用单独更新f[u][ans[u]],=f[v][ans[v]] 
        dp(son[u],u);
        ans[u]=ans[son[u]]+1;
    }
    //轻链顶暴力合并
    for(int i=first[u];i;i=e[i].ne){
        int v=e[i].v; if(v==fa || v==son[u]) continue;
        f[v]=p; p+=len[v];//分配内存 
        dp(v,u);
        E(j,len[v]){
            f[u][j]+=f[v][j-1];
            if(f[u][j]>f[u][ans[u]] || f[u][j]==f[u][ans[u]]&&ans[u]>j) ans[u]=j;
            //f[i][k]最大且k最小 
            //注意不能更新f[u][len[v]+1]
            //f[u][k]的k表示的是离u的距离,或者说是u这条长链的长度,
            //len[v]表示的是v的长链长度
            //换言之len[v]就是u的长链中在u下方的点的个数,就是u这条长链的长度!!! 
        }
    }        
    if(f[u][ans[u]]==1) ans[u]=0;//修正:上述两种情况没有同k=0做过比较 
}
int main(){
//    freopen("a.in","r",stdin);
//    freopen("a.out","w",stdout);
    n=rd(); int x,y; E(i,n-1){
        x=rd(); y=rd(); add(x,y); add(y,x);
    }
    dfs(1,0); E(i,n) 
    f[1]=p; p+=len[1]; //每次给链顶分配链长的内存 
    dp(1,0);
    E(i,n) printf("%d\n",ans[i]);
    return 0; 
}