树链剖分[学习笔记]

· 浏览次数 : 0

小编点评

The following is the solution to the problem: ```cpp #include<bits/stdc++.h>using namespace std;#define swap(x,y) (x^=y,y^=x,x^=y) void write(int x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); return;} using namespace Tree_Chain_Partition;int u[N],v[N],lca[N],len[N];int b[N];int sum,reduce;void dfs(int x){ for(int i=head[x];i;i=e[i].next){ int y=e[i].to; if(y==fa[x]) continue; dfs(y); b[x]+=b[y]; } if(b[x]==sum) reduce=max(reduce,e[edge[x]].t);}bool check(int x){ for(int i=1;i<=n;i++) b[i]=0; sum=reduce=0; for(int i=1;i<=m;i++){ if(len[i]>x){ sum++; b[u[i]]++; b[v[i]]++; b[lca[i]]-=2; } } dfs(1); if(MAX-reduce<=x) return 1; return 0;}int ans;signed main(){ #ifndef ONLINE_JUDGE freopen(\"lty.in\",\"r\",stdin); freopen(\"lty.out\",\"w\",stdout); #endif n=read,m=read; for(int a,b,c,i=1;i<n;i++){ a=read,b=read,c=read; add(a,b,c),add(b,a,c); } dfs1(1),dfs2(1,1); for(int i=1;i<=m;i++){ u[i]=read,v[i]=read; lca[i]=LCA(u[i],v[i]); len[i]=dis[u[i]]+dis[v[i]]-2*dis[lca[i]]; MAX=max(MAX,len[i]); } int st=0,ed=MAX; while(st<ed){ int mid=(st+ed)>>1; if(check(mid)) ed=ans=mid; else st=mid+1; } write(ans); return 0;} ```

正文

树链剖分

壹.

树剖，就是树链剖分，将一棵树剖分成一堆链 (如说 \(\dots\) )

本文主要介绍重链剖分。

树剖成链之后一段重链上的 \(dfs\) 序是连续的，那么我们就可以对 \(dfs\) 序使用一些数据结构(树状数组、线段树等)

\(1\).一些变量及意义

  • \(fa[x]\) \(x\) 的父节点
  • \(depth[x]\) \(x\) 的深度
  • \(siz[x]\) \(x\) 的子树大小，我们将根据他求重儿子
  • \(wson[x]\) \(x\) 的重儿子，即 \(x\) 的儿子中子树最大的
  • \(top[x]\) \(x\) 所在重链的链顶
  • \(dfn[x]\) \(x\) 的 \(dfs\) 序，即第二次访问到 \(x\) 的时间
  • \(id[i]\) 用来求 \(dfs\) 序为 \(i\) 的节点，即 \(id[dfn[x]]=x\)
  • \(out[x]\) 第二次访问到 \(x\) 的时间

说白了，树剖就是用来求上述东西，然后就可以利用上述东西搞事情了。

\(2\).两遍 \(dfs\) 完成树剖

  • 第一遍，我们可以轻松求出 \(fa[x]\)，\(depth[x]\)，\(siz[x]\)，\(wson[x]\)。
void dfs(int x){
    depth[x]=depth[fa[x]]+1;
    siz[x]=1;
    for(int i=head[x];i;i=e[i].next){
        int y=e[i].to;
        if(y==fa[x])  continue;
        fa[y]=x;
        dfs(y);
        if(siz[y]>siz[wson[x]])  wson[x]=y;//更新重儿子
        siz[x]+=siz[y];
    }
}

偷的图

  • 第二遍，主要求 \(dfs\) 序，顺便求下 \(top\) 。我们优先跑重儿子，就可以保证重链上的 \(dfs\) 序连续。
void dfs(int x,int tp){
    top[x]=tp;
    dfn[x]=++t;id[t]=x;
    if(wson[x])  dfs(wson[x],tp);
    for(int i=head[x];i;i=e[i].next){
        int y=e[i].to;
        if(y==fa[x]||y==wson[x])  continue;
        dfs(y,y);//显然，轻儿子一定是重链的链顶
    }
    out[x]=t;
}

\(3\).求 \(LCA\)

我们从 \(u,v\) 分别上跳，跳到链顶，为了防止它们 像小H和小C一样 错过，所以我们每次选择链顶深度大的上跳，到一条链上后，深度小的即为 \(LCA\)。

int LCA(int u,int v){
    while(top[u]!=top[v]){
        if(depth[top[u]]<depth[top[v]])  swap(u,v);
        u=fa[top[u]];
    }
    return (depth[u]<depth[v] ? u : v);
}

跳重链的复杂度为 \(O(\log _2n)\) 但是它严格跑不满，所以它的速度薄纱倍增和 \(tarjan\) 。

\(4\).一些性质和利用

  • 树剖成链之后一段重链上的 \(dfs\) 序是连续的，用线段树等即可优秀地维护重链信息
  • 从任意节点跳到根节点最多跳 \(\log _2n\) 次，多数情况下跑不满。

之前总听人说树剖码量大，学了之后才发现树剖就那么几行，不太会变，真正码量大的是维护重链信息的数据结构——比如线段树。如果你对线段树很怵头，先学好线段树吧，或者说，打完树剖你也就不怵头了。

贰.\(hs\)题单

\(T_A\) ZJOI2008 树的统计

板子，树剖，线段树维护单点修改，最大值和区间和，跳重链求解即可。

注意此题值域 \([-30000,30000]\) ，求最大值时注意初值赋极小

$CODE$ 
#include<bits/stdc++.h>
using namespace std;
#define swap(x,y) (x^=y,y^=x,x^=y)
#define read read()
#define pt puts("")
inline int read{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x){
    if(x<0)  putchar('-'),x=-x;
    if(x>9)  write(x/10);
    putchar(x%10+'0');
    return;
}
const int N=3*1e4+10;
#define INF 30010
int n;
int w[N];
struct EDGE{int next,to;}e[N<<1];
int head[N],total;
void add(int u,int v){e[++total]={head[u],v};head[u]=total;}

namespace Tree_Chain_Partition{
    int fa[N],depth[N],wson[N],siz[N];
    int top[N],dfn[N],id[N],out[N],t;
    void dfs1(int x){
        depth[x]=depth[fa[x]]+1;
        siz[x]=1;
        for(int i=head[x];i;i=e[i].next){
            int y=e[i].to;
            if(y==fa[x])  continue;
            fa[y]=x;
            dfs1(y);
            if(siz[y]>siz[wson[x]])  wson[x]=y;
            siz[x]+=siz[y];
        }
    }
    void dfs2(int x,int tp){
        top[x]=tp;
        dfn[x]=++t;id[t]=x;
        if(wson[x])  dfs2(wson[x],tp);
        for(int i=head[x];i;i=e[i].next){
            int y=e[i].to;
            if(y==fa[x]||y==wson[x])  continue;
            dfs2(y,y);
        }
        out[x]=t;
    }
    int LCA(int u,int v){
        while(top[u]!=top[v]){
            if(depth[top[u]]<depth[top[v]])  swap(u,v);
            u=fa[top[u]];
        }
        return (depth[u]<depth[v]?u:v);
    }
} using namespace Tree_Chain_Partition;

namespace Segment_Tree{
    struct Tree{
        int sum,mx,l,r;
        #define l(i) tr[i].l
        #define r(i) tr[i].r
        #define sum(i) tr[i].sum
        #define mx(i) tr[i].mx
        #define ls(i) (i<<1)
        #define rs(i) (i<<1|1)
    }tr[N<<2];
    void pushup(int i){
        sum(i)=sum(ls(i))+sum(rs(i));
        mx(i)=max(mx(ls(i)),mx(rs(i)));
    }
    void build(int i,int l,int r){
        l(i)=l;r(i)=r;
        if(l==r){
            mx(i)=sum(i)=w[id[l]];
            return;
        }
        int mid=(l+r)>>1;
        build(ls(i),l,mid);build(rs(i),mid+1,r);
        pushup(i);
        return;
    }
    void modify(int i,int x,int k){
        if(l(i)==r(i)){
            sum(i)=mx(i)=k;
            return;
        }
        int mid=(l(i)+r(i))>>1;
        if(x<=mid)  modify(ls(i),x,k);
        else  modify(rs(i),x,k);
        pushup(i);
        return;
    }
    int asksum(int i,int ql,int qr){
        int l=l(i),r=r(i);
        if(ql<=l&&r<=qr)  return sum(i);
        int mid=(l+r)>>1,res=0;;
        if(ql<=mid)  res+=asksum(ls(i),ql,qr);
        if(mid<qr)  res+=asksum(rs(i),ql,qr);
        return res;  
    }
    int askmax(int i,int ql,int qr){
        int l=l(i),r=r(i);
        if(ql<=l&&r<=qr)  return mx(i);
        int mid=(l+r)>>1,res=-INF;
        if(ql<=mid)  res=max(res,askmax(ls(i),ql,qr));
        if(mid<qr)  res=max(res,askmax(rs(i),ql,qr));
        return res;
    }
}using namespace Segment_Tree;
int ans;

int qsum(int u,int lca){
    int res=0;
    while(depth[top[u]]>depth[lca]&&top[u]!=top[lca]){
        res+=asksum(1,dfn[top[u]],dfn[u]);
        u=fa[top[u]];
    }
    res+=(u==lca?w[u]:asksum(1,dfn[lca],dfn[u]));
    return res;
}

int qmax(int u,int lca){
    int res=-INF;
    while(depth[top[u]]>depth[lca]&&top[u]!=top[lca]){
        res=max(res,askmax(1,dfn[top[u]],dfn[u]));
        u=fa[top[u]];
    }
    res=max(res,(u==lca?w[u]:askmax(1,dfn[lca],dfn[u])));
    return res;
}

signed main()
{
    #ifndef ONLINE_JUDGE
        freopen("lty.in","r",stdin);
        freopen("lty.out","w",stdout);
    #endif
    n=read;
    for(int i=1,a,b;i<n;i++)  a=read,b=read,add(a,b),add(b,a);
    for(int i=1;i<=n;i++)  w[i]=read;
    dfs1(1);dfs2(1,1);
    build(1,1,t);
    int T;T=read;
    char op[7];int u,v,k;
    while(T-->0){
        scanf("%s",op);u=read;
        if(op[0]=='C'){
            k=read;w[u]=k;
            modify(1,dfn[u],k);
        }
        else{
            v=read;
            int lca=LCA(u,v);
            if(op[1]=='S'){
                ans=-w[lca];
                ans+=qsum(u,lca);
                ans+=qsum(v,lca);
            }
            else{
                ans=-INF;
                ans=max(ans,qmax(u,lca));
                ans=max(ans,qmax(v,lca));
            }
            write(ans),pt;
        }
    }

    return 0;
}

\(T_B\) HAOI2015 树上操作

板子，树剖，线段树维护区间修改区间求和。

$CODE$ 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define read read()
#define pt puts("")
inline int read{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x){
    if(x<0)  putchar('-'),x=-x;
    if(x>9)  write(x/10);
    putchar(x%10+'0');
    return;
}
#define N 100010
int n,w[N];
int m;

namespace Tree_Chain_Partition{
    struct EDGE{int next,to;}e[N<<1];
    int head[N],total;
    void add(int u,int v){e[++total]={head[u],v};head[u]=total;}
    int fa[N],wson[N],depth[N],siz[N];
    int top[N],dfn[N],out[N],id[N],t;
    void dfs1(int x){
        depth[x]=depth[fa[x]]+1;
        siz[x]=1;
        for(int i=head[x];i;i=e[i].next){
            int y=e[i].to;
            if(y==fa[x])  continue;
            fa[y]=x;
            dfs1(y);
            if(siz[y]>siz[wson[x]])  wson[x]=y;
            siz[x]+=siz[y];
        }
    }
    void dfs2(int x,int tp){
        top[x]=tp;
        dfn[x]=++t;id[t]=x;
        if(wson[x])  dfs2(wson[x],tp);
        for(int i=head[x];i;i=e[i].next){
            int y=e[i].to;
            if(y==fa[x]||y==wson[x])  continue;
            dfs2(y,y);
        }
        out[x]=t;
    }
} using namespace Tree_Chain_Partition;

namespace Segment_Tree{
    struct Tree{
        int l,r,sum,lazy;
        #define l(i) tr[i].l
        #define r(i) tr[i].r
        #define sum(i) tr[i].sum
        #define lazy(i) tr[i].lazy
        #define ls(i) (i<<1)
        #define rs(i) (i<<1|1)
    }tr[N<<2];
    void pushup(int i){sum(i)=sum(ls(i))+sum(rs(i));}
    void pushdown(int i){
        if(!lazy(i))  return;
        sum(ls(i))+=(r(ls(i))-l(ls(i))+1)*lazy(i);
        sum(rs(i))+=(r(rs(i))-l(rs(i))+1)*lazy(i);
        lazy(ls(i))+=lazy(i);
        lazy(rs(i))+=lazy(i);
        lazy(i)=0;
        return;
    }
    void build(int i,int l,int r){
        l(i)=l,r(i)=r;
        if(l==r){
            sum(i)=w[id[l]];
            return;
        }
        int mid=(l+r)>>1;
        build(ls(i),l,mid);build(rs(i),mid+1,r);
        pushup(i);
        return;
    }
    void modify(int i,int x,int k){
        int l=l(i),r=r(i);
        if(l==r){
            sum(i)+=k;
            return;
        }
        pushdown(i);
        int mid=(l+r)>>1;
        if(x<=mid)  modify(ls(i),x,k);
        else  modify(rs(i),x,k);
        pushup(i);
        return;
    }
    void update(int i,int ml,int mr,int k){
        int l=l(i),r=r(i);
        if(ml<=l&&r<=mr){
            lazy(i)+=k;
            sum(i)+=(r(i)-l(i)+1)*k;
            return;
        }
        pushdown(i);
        int mid=(l+r)>>1;
        if(ml<=mid)  update(ls(i),ml,mr,k);
        if(mid<mr)  update(rs(i),ml,mr,k);
        pushup(i);
        return;
    }
    int query(int i,int ql,int qr){
        int l=l(i),r=r(i);
        if(ql<=l&&r<=qr)  return sum(i);
        pushdown(i);
        int mid=(l+r)>>1,res=0;
        if(ql<=mid)  res+=query(ls(i),ql,qr);
        if(mid<qr)  res+=query(rs(i),ql,qr);
        pushup(i);
        return res;
    }

} using namespace Segment_Tree;


signed main()
{
    #ifndef ONLINE_JUDGE
        freopen("lty.in","r",stdin);
        freopen("lty.out","w",stdout);
    #endif
    n=read;m=read;
    for(int i=1;i<=n;i++)  w[i]=read;
    for(int i=1,a,b;i<n;i++)  a=read,b=read,add(a,b),add(b,a);
    dfs1(1);dfs2(1,1);
    build(1,1,t);
    int op,u,v,k,ans;
    while(m-->0){
        op=read;u=read;
        switch(op){
        case 1:
            k=read;
            modify(1,dfn[u],k);
            break;
        case 2:
            k=read;
            update(1,dfn[u],out[u],k);
            break;
        case 3:
            ans=0;
            while(u){
                ans+=query(1,dfn[top[u]],dfn[u]);
                u=fa[top[u]];
            }
            write(ans);pt;
            break;
        default:break;
        }
    }

    return 0;
}

\(T_C\) 难存的情缘

vjudge上没找着，挂学校OJ吧

板子，树剖，将边权下放到点上，然后单点修改区间查询最大值即可。

$CODE$ 
#include<bits/stdc++.h>
using namespace std;

#define read read()
#define pt puts("")
inline int read{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x){
    if(x<0)  putchar('-'),x=-x;
    if(x>9)  write(x/10);
    putchar(x%10+'0');
    return;
}
#define N 10010
int n,w[N];

namespace Tree_Chain_Partition{
    struct EDGE{int next,to,ww,number;}e[N<<1];
    int head[N],total;int dot[N];
    void add(int u,int v,int ww,int id){e[++total]={head[u],v,ww,id};head[u]=total;}

    int fa[N],depth[N],wson[N],siz[N];
    int top[N],dfn[N],id[N],t;
    void dfs1(int x){
        depth[x]=depth[fa[x]]+1;
        siz[x]=1;
        for(int i=head[x];i;i=e[i].next){
            int y=e[i].to;
            if(y==fa[x])  continue;
            fa[y]=x;
            // cerr<<x<<"->"<<y<<'\n';
            // cerr<<"e["<<i<<"].num="<<e[i].number<<'\n';
            // cerr<<"e["<<i<<"].ww="<<e[i].ww<<'\n';
            dot[e[i].number]=y;
            w[y]=e[i].ww;
            dfs1(y);
            if(siz[y]>siz[wson[x]])  wson[x]=y;
            siz[x]+=siz[y];
        }
    }
    void dfs2(int x,int tp){
        top[x]=tp;
        dfn[x]=++t;id[t]=x;
        if(wson[x])  dfs2(wson[x],tp);
        for(int i=head[x];i;i=e[i].next){
            int y=e[i].to;
            if(y==fa[x]||y==wson[x])  continue;
            dfs2(y,y);
        }
    }
} using namespace Tree_Chain_Partition;

namespace Segment_Tree{
    struct Tree{
        int l,r,mx;
        #define ls(i) (i<<1)
        #define rs(i) (i<<1|1)
        #define l(i) tr[i].l
        #define r(i) tr[i].r
        #define mx(i) tr[i].mx
    }tr[N<<2];
    void pushup(int i){mx(i)=max(mx(ls(i)),mx(rs(i)));}
    void build(int i,int l,int r){
        l(i)=l,r(i)=r;
        if(l==r){
            mx(i)=w[id[l]];
            return;
        }
        int mid=(l+r)>>1;
        build(ls(i),l,mid);build(rs(i),mid+1,r);
        pushup(i);
        return;
    }
    void modify(int i,int x,int k){
        int l=l(i),r=r(i);
        if(l==r){
            mx(i)=k;
            return;
        }
        int mid=(l+r)>>1;
        if(x<=mid)  modify(ls(i),x,k);
        else  modify(rs(i),x,k);
        pushup(i);
        return;
    }
    int query(int i,int ql,int qr){
        int l=l(i),r=r(i);
        if(ql<=l&&r<=qr){
            return mx(i);
        }
        int mid=(l+r)>>1,res=0;
        if(ql<=mid)  res=max(res,query(ls(i),ql,qr));
        if(mid<qr)  res=max(res,query(rs(i),ql,qr));
        return res;
    }
} using namespace Segment_Tree;


signed main()
{
    #ifndef ONLINE_JUDGE
        freopen("lty.in","r",stdin);
        freopen("lty.out","w",stdout);
    #endif
    n=read;
    for(int a,b,c,i=1;i<n;i++){
        a=read,b=read,c=read;
        add(a,b,c,i);add(b,a,c,i);
    }
    dfs1(1);dfs2(1,1);
    build(1,1,t);
    char op[7];
    int u,v,k,i,ans;
    while(1){
        scanf("%s",op);
        switch(op[0]){
        case 'C':
            i=read,k=read;
            u=dot[i];
            modify(1,dfn[u],k);
            break;
        case 'Q':
            u=read,v=read;ans=0;
            while(top[u]!=top[v]){
                if(depth[top[u]]<depth[top[v]])  swap(u,v);
                ans=max(ans,query(1,dfn[top[u]],dfn[u]));
                u=fa[top[u]];
            }
            ans=max(ans,(depth[u]<depth[v]?query(1,dfn[wson[u]],dfn[v]):query(1,dfn[wson[v]],dfn[u])));
            write(ans);pt;
            break;
        default:
            return 0;
        }
    }

    return 0;
}

\(T_D\) 货车运输

打 \(LCA\) 时打过一次，一样的思路，把倍增换成树剖。

首先一个 \(kruskal\) 重构树，然后就很板了，树剖，线段树维护区间最小值。

$CODE$ 
#include<bits/stdc++.h>
using namespace std;
#define swap(x,y) (x^=y,y^=x,x^=y)
#define read read()
#define pt puts("")
inline int read{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x){
    if(x<0)  putchar('-'),x=-x;
    if(x>9)  write(x/10);
    putchar(x%10+'0');
    return;
}
#define N 20010
#define M 50010
int n,m;
int w[N<<1];
namespace klskr{
    struct EDGE{int next,from,to,w;}e[M<<1],q[M<<1];
    int head[N],total,hq[N],tot;
    void add(int u,int v,int w){e[++total]={head[u],u,v,w};head[u]=total;}
    void addq(int u,int v){
        tot++;
        q[tot].next=hq[u];
        q[tot].to=v;
        hq[u]=tot;
    }
    int rt[N];
    int find(int x){return rt[x]==x?x:(rt[x]=find(rt[x]));}
} using namespace klskr;

namespace Tree_Chain_Partition{
    int fa[N],siz[N],depth[N],wson[N];
    int top[N],dfn[N],id[N],t;
    void dfs1(int x){
        depth[x]=depth[fa[x]]+1;
        siz[x]=1;
        for(int i=hq[x];i;i=q[i].next){
            int y=q[i].to;
            if(y==fa[x])  continue;
            fa[y]=x;
            dfs1(y);
            if(siz[y]>siz[wson[x]])  wson[x]=y;
            siz[x]+=siz[y];
        }
    }
    void dfs2(int x,int tp){
        top[x]=tp;
        dfn[x]=++t;id[t]=x;
        if(wson[x])  dfs2(wson[x],tp);
        for(int i=hq[x];i;i=q[i].next){
            int y=q[i].to;
            if(y==wson[x]||y==fa[x])  continue;
            dfs2(y,y);
        }
    }
} using namespace Tree_Chain_Partition;

namespace Segment_Tree{
    struct Tree{
        int l,r,minn;
        #define l(i) tr[i].l
        #define r(i) tr[i].r
        #define ls(i) (i<<1)
        #define rs(i) (i<<1|1)
        #define minn(i) tr[i].minn
    }tr[N<<2];
    void build(int i,int l,int r){
        l(i)=l,r(i)=r;
        if(l==r){
            minn(i)=w[id[l]];
            return;
        }
        int mid=(l+r)>>1;
        build(ls(i),l,mid);
        build(rs(i),mid+1,r);
        minn(i)=min(minn(ls(i)),minn(rs(i)));
        return;
    }
    int query(int i,int ql,int qr){
        int l=l(i),r=r(i);
        if(ql<=l&&r<=qr)  return minn(i);
        int mid=(l+r)>>1,res=1e8;
        if(ql<=mid)  res=min(res,query(ls(i),ql,qr));
        if(mid<qr)  res=min(res,query(rs(i),ql,qr));
        return res;
    }
} using namespace Segment_Tree;


signed main()
{
    #ifndef ONLINE_JUDGE
        freopen("lty.in","r",stdin);
        freopen("lty.out","w",stdout);
    #endif
    n=read,m=read;
    for(int i=1;i<=(n<<1);i++)  rt[i]=i,w[i]=1e8;
    for(int i=1,a,b,c;i<=m;i++)  a=read,b=read,c=read,add(a,b,c),add(b,a,c);
    sort(e+1,e+total+1,[](EDGE a,EDGE b){return a.w>b.w;});
    for(int i=1;i<=total;i++){
        EDGE x=e[i];
        int u=x.from,v=x.to;
        int uu=find(u),vv=find(v);
        if(uu!=vv){
            rt[uu]=rt[vv]=++n;
            addq(n,uu);addq(uu,n);
            addq(n,vv),addq(vv,n);
            w[n]=x.w;
        }
    }
    for(int i=n;i>=1;i--){
        if(!dfn[i]){
            dfs1(i);
            dfs2(i,i);
        }
    }
    build(1,1,t);
    int T,u,v,ans;
    T=read;
    while(T-->0){
        u=read,v=read;
        int uu=find(u),vv=find(v);
        if(uu!=vv){
            puts("-1");
            continue;
        }
        ans=1e8;
        while(top[u]!=top[v]){
            if(depth[top[u]]<depth[top[v]])  swap(u,v);
            ans=min(ans,query(1,dfn[top[u]],dfn[u]));
            u=fa[top[u]];
        }
        ans=min(ans,(depth[u]<depth[v] ? query(1,dfn[u],dfn[v]) : query(1,dfn[v],dfn[u])));
        write(ans);pt;
    }

    return 0;
}

\(T_E\) 遥远的国度

涉及换根，那就换，我们"假装"换，(用一个变量 \(rt\) 存储当前的根，直接换)，但实际根仍为 \(1\)，树剖，线段树维护单点修改和区间最小值，单点修改不变，对于区间最小值:

  1. \(rt=u\) 查整棵树。
  2. \(rt\) 不在 \(u\) 子树里，该查啥查啥。
  3. \(rt\) 在 \(u\) 子树里，考虑将查询区间分成两段，设 \(v\) 为 \(u\) 在 \(rt\) 方向上的儿子，答案显然是总答案减去去 \(v\) 的子树的贡献，即分成 \([1,dfn[v]-1]\) 和 \([out[v]+1,t]\) 两段答案进行统计即可。

对于换根我们的大体思路就是这样。

$CODE$ 
#include<bits/stdc++.h>
using namespace std;
#define swap(x,y) (x^=y,y^=x,x^=y)
#define int long long
#define read read()
#define pt puts("")
inline int read{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x){
    if(x<0)  putchar('-'),x=-x;
    if(x>9)  write(x/10);
    putchar(x%10+'0');
    return;
}
#define N 100010
const int MAX=1e10;
int n,m,rt;
int w[N];
struct EDGE{int next,to;}e[N<<1];
int head[N],total;
void add(int u,int v){ e[++total]={head[u],v}; head[u]=total;}

namespace Tree_Chain_Partition{
    int fa[N],siz[N],wson[N],depth[N];
    int dfn[N],out[N],id[N],t,top[N];
    void dfs(int x){
        depth[x]=depth[fa[x]]+1;
        siz[x]=1;
        for(int i=head[x];i;i=e[i].next){
            int y=e[i].to;
            if(y==fa[x])  continue;
            fa[y]=x;
            dfs(y);
            if(siz[y]>siz[wson[x]])  wson[x]=y;
            siz[x]+=siz[y];
        }
    }
    void dfs(int x,int tp){
        top[x]=tp;
        dfn[x]=++t;id[t]=x;
        if(wson[x])  dfs(wson[x],tp);
        for(int i=head[x];i;i=e[i].next){
            int y=e[i].to;
            if(y==fa[x]||y==wson[x])  continue;
            dfs(y,y);
        }
        out[x]=t;
    }
} using namespace Tree_Chain_Partition;

namespace Segment_Tree{
    struct Tree{
        int l,r,minn,lazy;
        #define l(i) tr[i].l
        #define r(i) tr[i].r
        #define minn(i) tr[i].minn
        #define lazy(i) tr[i].lazy
        #define ls(i) (i<<1)
        #define rs(i) (i<<1|1)
    }tr[N<<2];
    void pushup(int i){minn(i)=min(minn(ls(i)),minn(rs(i)));}
    void pushdown(int i){
        if(!lazy(i)) return;
        minn(ls(i))=minn(rs(i))=lazy(ls(i))=lazy(rs(i))=lazy(i);
        lazy(i)=0;
        return;
    }
    void build(int i,int l,int r){
        l(i)=l,r(i)=r;
        if(l==r){
            minn(i)=w[id[l]];
            return;
        }
        int mid=(l+r)>>1;
        build(ls(i),l,mid);
        build(rs(i),mid+1,r);
        pushup(i);
        return;
    }
    void update(int i,int ul,int ur,int k){
        int l=l(i),r=r(i);
        if(ul<=l&&r<=ur){
            minn(i)=lazy(i)=k;
            return;
        }
        pushdown(i);
        int mid=(l+r)>>1;
        if(ul<=mid)  update(ls(i),ul,ur,k);
        if(mid<ur)  update(rs(i),ul,ur,k);
        pushup(i);
        return;
    }
    int query(int i,int ql,int qr){
        int l=l(i),r=r(i);
        if(ql<=l&&r<=qr){
            return minn(i);
        }
        pushdown(i);
        int mid=(l+r)>>1,res=MAX;
        if(ql<=mid)  res=min(res,query(ls(i),ql,qr));
        if(mid<qr)  res=min(res,query(rs(i),ql,qr));
        pushup(i);
        return res;
    }
} using namespace Segment_Tree;

signed main()
{
    #ifndef ONLINE_JUDGE
        freopen("lty.in","r",stdin);
        freopen("lty.out","w",stdout);
    #endif
    n=read,m=read;
    for(int a,b,i=1;i<n;i++){
        a=read,b=read;
        add(a,b),add(b,a);
    }
    for(int i=1;i<=n;i++)  w[i]=read;
    dfs(1);dfs(1,1);
    build(1,1,t);
    rt=read;
    int op,u,v,k,ans;
    while(m-->0){
        op=read;
        switch(op){
        case 1:
            rt=read;
            break;
        case 2:
            u=read,v=read,k=read;
            while(top[u]!=top[v]){
                if(depth[top[u]]<depth[top[v]])  swap(u,v);
                update(1,dfn[top[u]],dfn[u],k);
                u=fa[top[u]];
            }
            depth[u]<depth[v] ? update(1,dfn[u],dfn[v],k) : update(1,dfn[v],dfn[u],k);
            break;
        case 3:
            u=read;ans=MAX;
            if(u==rt)  ans=minn(1);
            else if(dfn[u]<dfn[rt]&&dfn[rt]<=out[u]){
                v=rt;
                while(top[u]!=top[v]){
                    if(fa[top[v]]==u){
                        v=top[v];break;
                    }
                    v=fa[top[v]];
                }
                if(fa[v]!=u)  v=wson[u];
                if(dfn[v]-1>=1)  ans=min(ans,query(1,1,dfn[v]-1));
                if(out[v]+1<=t)  ans=min(ans,query(1,out[v]+1,t));
            }
            else
                ans=query(1,dfn[u],out[u]);
            write(ans);pt;
            break;
        default:
            break;
        }
    }
    return 0;
}

对于换根，还可以求 \(LCA\)，比如 Jamie and Tree，我们可以分讨归纳证明，节点 \(u,v\) 在根为 \(rt\) 时的 \(LCA\) 为 \(lca(u,v),lca(u,rt),lca(v,rt)\) 中深度最大的节点，其他的按照上面的思路维护即可。

$CODE$ 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define read read()
#define pt puts("")
inline int read{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x){
    if(x<0)  putchar('-'),x=-x;
    if(x>9)  write(x/10);
    putchar(x%10+'0');
    return;
}
const int N=1e5+10;
int n,q;
int w[N];
struct EDGE{int next,to;}e[N<<1];
int head[N],total,rt=1;
void add(int u,int v){e[++total]={head[u],v};head[u]=total;}

namespace Tree_Chain_Partition{
    int fa[N],depth[N],siz[N],wson[N];
    int top[N],dfn[N],out[N],id[N],t;
    void dfs(int x){
        depth[x]=depth[fa[x]]+1;
        siz[x]=1;
        for(int i=head[x];i;i=e[i].next){
            int y=e[i].to;
            if(y==fa[x])  continue;
            fa[y]=x;
            dfs(y);
            if(siz[y]>siz[wson[x]])  wson[x]=y;
            siz[x]+=siz[y];
        }
    }
    void dfs(int x,int tp){
        top[x]=tp;
        dfn[x]=++t;id[t]=x;
        if(wson[x])  dfs(wson[x],tp);
        for(int i=head[x];i;i=e[i].next){
            int y=e[i].to;
            if(y==fa[x]||y==wson[x])  continue;
            dfs(y,y);
        }
        out[x]=t;
    }
    int LCA(int u,int v){
        while(top[u]!=top[v]){
            if(depth[top[u]]<depth[top[v]])  swap(u,v);
            u=fa[top[u]];
        }
        return (depth[u]<depth[v] ? u : v);
    }
    int findson(int u,int rt){//查询u在rt方向上的儿子
        int v=rt;
        while(top[v]!=top[u]){
            if(fa[top[v]]==u){
                v=top[v];break;
            }
            v=fa[top[v]];
        }
        if(fa[v]!=u)  v=wson[u];
        return v;
    }
} using namespace Tree_Chain_Partition;

namespace Segment_Tree{
    struct Tree{
        int l,r,sum,lazy;
        #define l(i) tr[i].l
        #define r(i) tr[i].r
        #define sum(i) tr[i].sum
        #define lazy(i) tr[i].lazy
        #define ls(i) (i<<1)
        #define rs(i) (i<<1|1)
    }tr[N<<2];
    void pushup(int i){sum(i)=sum(ls(i))+sum(rs(i));}
    void pushdown(int i){
        if(!lazy(i)) return;
        sum(ls(i))+=(r(ls(i))-l(ls(i))+1)*lazy(i);
        sum(rs(i))+=(r(rs(i))-l(rs(i))+1)*lazy(i);
        lazy(ls(i))+=lazy(i),lazy(rs(i))+=lazy(i);
        lazy(i)=0;
        return;
    }
    void build(int i,int l,int r){
        l(i)=l,r(i)=r;
        if(l==r){
            sum(i)=w[id[l]];
            return;
        }
        int mid=(l+r)>>1;
        build(ls(i),l,mid);
        build(rs(i),mid+1,r);
        pushup(i);
        return;
    }
    void update(int i,int ul,int ur,int k){
        int l=l(i),r=r(i);
        if(ul<=l&&r<=ur){
            lazy(i)+=k;
            sum(i)+=(r-l+1)*k;
            return;
        }
        pushdown(i);
        int mid=(l+r)>>1;
        if(ul<=mid)  update(ls(i),ul,ur,k);
        if(mid<ur)  update(rs(i),ul,ur,k);
        pushup(i);
        return;
    }
    int query(int i,int ql,int qr){
        int l=l(i),r=r(i);
        if(ql<=l&&r<=qr){
            return sum(i);
        }
        pushdown(i);
        int mid=(l+r)>>1,res=0;
        if(ql<=mid)  res+=query(ls(i),ql,qr);
        if(mid<qr)  res+=query(rs(i),ql,qr);
        pushup(i);
        return res;
    }
} using namespace Segment_Tree;

signed main()
{
    #ifndef ONLINE_JUDGE
        freopen("lty.in","r",stdin);
        freopen("lty.out","w",stdout);
    #endif
    n=read,q=read;
    for(int i=1;i<=n;i++)  w[i]=read;
    for(int a,b,i=1;i<n;i++){
        a=read,b=read;add(a,b),add(b,a);
    }
    dfs(1);dfs(1,1);
    build(1,1,t);
    int op,u,v,k,ans;
    int lca,lca1,lca2,lca3;
    while(q-->0){
        op=read;
        switch(op){
            case 1:
                rt=read;
                break;
            case 2:
                u=read,v=read,k=read;
                lca1=LCA(u,v);
                lca2=LCA(u,rt);
                lca3=LCA(v,rt);
                lca=(depth[lca1]>depth[lca2] ? lca1 : lca2);
                lca=(depth[lca]>depth[lca3] ? lca : lca3);
                if(lca==rt)
                    update(1,1,t,k);
                
                else if(dfn[lca]<dfn[rt]&&dfn[rt]<=out[lca]){
                    v=findson(lca,rt);
                    if(dfn[v]-1>=1)  update(1,1,dfn[v]-1,k);
                    if(out[v]+1<=t)  update(1,out[v]+1,t,k);
                }
                else
                    update(1,dfn[lca],out[lca],k);
                break;
            case 3:
                u=read;
                ans=0;
                if(u==rt){
                    ans=query(1,1,t);
                }
                else if(dfn[u]<dfn[rt]&&dfn[rt]<=out[u]){
                    v=findson(u,rt);
                    if(dfn[v]-1>=1)  ans+=query(1,1,dfn[v]-1);
                    if(out[v]+1<=t)  ans+=query(1,out[v]+1,t);
                }
                else
                    ans=query(1,dfn[u],out[u]);
                write(ans),pt;
                break;
            default:break;
        }
    }

    return 0;
}

\(T_F\) 染色

思路差不多，多了点细节，线段树每个节点多维护一个 \(lc\) 和一个 \(rc\) 为每段左右端点的颜色，然后注意查完一段 \([dfn[top[u]],dfn[u]]\) 后，查一下 \(top[u]\) 和 \(fa[top[u]]\) 的颜色是否相同，相同就要让答案减一。

$CODE$ 
#include<bits/stdc++.h>
using namespace std;
#define swap(x,y) (x^=y,y^=x,x^=y)
#define read read()
#define pt puts("")
inline int read{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x){
    if(x<0)  putchar('-'),x=-x;
    if(x>9)  write(x/10);
    putchar(x%10+'0');
    return;
}
const int N=1e5+10;
#define M 400
int n,m;
int c[N];
struct EDGE{int next,to;}e[N<<1];
int head[N],total;
void add(int u,int v){e[++total]={head[u],v};head[u]=total;}

namespace Tree_Chain_Partition{
    int fa[N],siz[N],depth[N],wson[N];
    int top[N],dfn[N],id[N],t;
    void dfs(int x){
        depth[x]=depth[fa[x]]+1;
        siz[x]=1;
        for(int i=head[x];i;i=e[i].next){
            int y=e[i].to;
            if(y==fa[x])  continue;
            fa[y]=x;
            dfs(y);
            if(siz[y]>siz[wson[x]])  wson[x]=y;
            siz[x]+=siz[y];
        }
    }
    void dfs(int x,int tp){
        top[x]=tp;
        dfn[x]=++t;id[t]=x;
        if(wson[x])  dfs(wson[x],tp);
        for(int i=head[x];i;i=e[i].next){
            int y=e[i].to;
            if(y==fa[x]||y==wson[x])  continue;
            dfs(y,y);
        }
    }
} using namespace Tree_Chain_Partition;

namespace Segment_Tree{
    struct Tree{
        int l,r,cnt,lc,rc,lazy;
        #define l(i) tr[i].l
        #define r(i) tr[i].r
        #define cnt(i) tr[i].cnt
        #define lc(i) tr[i].lc
        #define rc(i) tr[i].rc
        #define lazy(i) tr[i].lazy
        #define ls(i) (i<<1)
        #define rs(i) (i<<1|1)
    }tr[N<<2];
    void pushup(int i){
        lc(i)=lc(ls(i)),rc(i)=rc(rs(i));
        cnt(i)=cnt(ls(i))+cnt(rs(i));
        if(rc(ls(i))==lc(rs(i)))  --cnt(i);
        return;
    }
    void pushdown(int i){
        if(!lazy(i))  return;
        lazy(ls(i))=lazy(rs(i))=lazy(i);
        lc(ls(i))=rc(ls(i))=lazy(i);
        lc(rs(i))=rc(rs(i))=lazy(i);
        cnt(ls(i))=cnt(rs(i))=1;
        lazy(i)=0;
        return;
    }
    void build(int i,int l,int r){
        l(i)=l,r(i)=r;
        if(l==r){
            lc(i)=rc(i)=c[id[l]];
            cnt(i)=1;
            return;
        }
        int mid=(l+r)>>1;
        build(ls(i),l,mid);
        build(rs(i),mid+1,r);
        pushup(i);
        return;
    }
    void update(int i,int ul,int ur,int k){
        int l=l(i),r=r(i);
        if(ul<=l&&r<=ur){
            lazy(i)=k;
            lc(i)=rc(i)=k;
            cnt(i)=1;
            return;
        }
        pushdown(i);
        int mid=(l+r)>>1;
        if(ul<=mid)  update(ls(i),ul,ur,k);
        if(mid<ur)  update(rs(i),ul,ur,k);
        pushup(i);
        return;
    }
    int ask(int i,int x){
        int l=l(i),r=r(i);
        if(l==r)  return lc(i);
        pushdown(i);
        int mid=(l+r)>>1,res;
        if(x<=mid)  res=ask(ls(i),x);
        else  res=ask(rs(i),x);
        pushup(i);
        return res;
    }
    int query(int i,int ql,int qr){
        int l=l(i),r=r(i);
        if(ql<=l&&r<=qr){
            return cnt(i);
        }
        pushdown(i);
        int mid=(l+r)>>1,res=0;
        if(ql<=mid&&mid<qr){
            if(rc(ls(i))==lc(rs(i)))  res--;
        }
        if(ql<=mid)  res+=query(ls(i),ql,qr);
        if(mid<qr)  res+=query(rs(i),ql,qr);
        pushup(i);
        return res;
    }
} using namespace Segment_Tree;

signed main()
{
    #ifndef ONLINE_JUDGE
        freopen("lty.in","r",stdin);
        freopen("lty.out","w",stdout);
    #endif
    n=read,m=read;
    for(int i=1;i<=n;i++)  c[i]=read;
    for(int a,b,i=1;i<n;i++){
        a=read,b=read;add(a,b),add(b,a);
    }
    dfs(1),dfs(1,1);
    build(1,1,t);
    char op;int u,v,k,ans;
    while(m-->0){
        op=getchar();while(op!='Q'&&op!='C') op=getchar();
        u=read,v=read;
        if(op=='Q'){
            ans=0;
            while(top[u]!=top[v]){
                if(depth[top[u]]<depth[top[v]])  swap(u,v);
                ans+=query(1,dfn[top[u]],dfn[u]);
                u=top[u];
                int a=ask(1,dfn[u]),b=ask(1,dfn[fa[u]]);
                if(a==b)  ans--;
                u=fa[u];
            }
            ans+=(depth[u]<depth[v] ? query(1,dfn[u],dfn[v]) : query(1,dfn[v],dfn[u]));
            write(ans);pt;
        }
        if(op=='C'){
            k=read;
            while(top[u]!=top[v]){
                if(depth[top[u]]<depth[top[v]])  swap(u,v);
                update(1,dfn[top[u]],dfn[u],k);
                u=fa[top[u]];
            }
            depth[u]<depth[v] ? update(1,dfn[u],dfn[v],k) : update(1,dfn[v],dfn[u],k);
        }
    }

    return 0;
}

\(T_G\) 运输计划

二分答案树上差分，几个月前打 \(LCA\) 时就打了，当时倍增就被卡了，树剖跑飞快。

$$ my blog $$

$CODE$ 
#include<bits/stdc++.h>
using namespace std;
#define swap(x,y) (x^=y,y^=x,x^=y)
#define read read()
#define pt puts("")
inline int read{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x){
    if(x<0)  putchar('-'),x=-x;
    if(x>9)  write(x/10);
    putchar(x%10+'0');
    return;
}
#define N 300010
int n,m;
int MAX;
struct EDGE{int next,to,t;}e[N<<1];
int head[N],total;
void add(int u,int v,int t){e[++total]={head[u],v,t};head[u]=total;}
int edge[N];
namespace Tree_Chain_Partition{
    int fa[N],siz[N],wson[N],depth[N];
    int top[N];
    int dis[N];
    void dfs1(int x){
        depth[x]=depth[fa[x]]+1;
        siz[x]=1;
        for(int i=head[x];i;i=e[i].next){
            int y=e[i].to;
            if(y==fa[x])  continue;
            edge[y]=i;
            dis[y]=dis[x]+e[i].t;
            fa[y]=x;
            dfs1(y);
            if(siz[y]>siz[wson[x]])  wson[x]=y;
            siz[x]+=siz[y];
        }
    }
    void dfs2(int x,int tp){
        top[x]=tp;
        if(wson[x])  dfs2(wson[x],tp);
        for(int i=head[x];i;i=e[i].next){
            int y=e[i].to;
            if(y==wson[x]||y==fa[x])  continue;
            dfs2(y,y);
        }
        
    }
    int LCA(int u,int v){
        while(top[u]!=top[v]){
            if(depth[top[u]]<depth[top[v]])  swap(u,v);
            u=fa[top[u]];
        }
        return (depth[u]<depth[v]?u:v);
    }
} using namespace Tree_Chain_Partition;
int u[N],v[N],lca[N],len[N];
int b[N];
int sum,reduce;
void dfs(int x){
    for(int i=head[x];i;i=e[i].next){
        int y=e[i].to;
        if(y==fa[x])  continue;
        dfs(y);
        b[x]+=b[y];
    }
    if(b[x]==sum)  reduce=max(reduce,e[edge[x]].t);
}
bool check(int x){
    for(int i=1;i<=n;i++)  b[i]=0;
    sum=reduce=0;
    for(int i=1;i<=m;i++){
        if(len[i]>x){
            sum++;
            b[u[i]]++;
            b[v[i]]++;
            b[lca[i]]-=2;
        }
    }
    dfs(1);
    if(MAX-reduce<=x)  return 1;
    return 0;
}

int ans;
signed main()
{
    #ifndef ONLINE_JUDGE
        freopen("lty.in","r",stdin);
        freopen("lty.out","w",stdout);
    #endif
    n=read,m=read;
    for(int a,b,c,i=1;i<n;i++){
        a=read,b=read,c=read;
        add(a,b,c),add(b,a,c);
    }
    dfs1(1),dfs2(1,1);
    for(int i=1;i<=m;i++){
        u[i]=read,v[i]=read;
        lca[i]=LCA(u[i],v[i]);
        len[i]=dis[u[i]]+dis[v[i]]-2*dis[lca[i]];
        MAX=max(MAX,len[i]);
    }
    int st=0,ed=MAX;
    while(st<ed){
        int mid=(st+ed)>>1;
        if(check(mid))
            ed=ans=mid;
        else
            st=mid+1;
    }
    write(ans);
    return 0;
}

与树链剖分[学习笔记]相似的内容：

树链剖分[学习笔记]

树链剖分 壹. 树剖，就是树链剖分，将一棵树剖分成一堆链 (如说 \(\dots\) ) 本文主要介绍重链剖分。 树剖成链之后一段重链上的 \(dfs\) 序是连续的，那么我们就可以对 \(dfs\) 序使用一些数据结构(树状数组、线段树等) \(1\).一些变量及意义 \(fa[x]\) \(x\

0
算法学习笔记(6): 树链剖分

树链剖分 树链剖分是一个很神奇，但是在树上可以完成一些区间操作问题 简单来说，就是把一棵树分成一条条的链，通过维护链上的信息来维护整棵树的信息 基础知识可以参考我的另外一篇博客：算法学习笔记(5): 最近公共祖先(LCA) 这里假设你已经掌握了上述博客中的所有相关知识，并清晰了其背后的原理 性质？发

算法 学习 笔记
39
平衡树 Treap & Splay [学习笔记]

平衡树 \(\tt{Treap}\) & \(\tt{Splay}\) 壹.单旋 \(\tt{Treap}\) 首先了解 \(\tt{BST}\) 非常好用的东西，但是数据可以把它卡成一条链 \(\dots\) 于是，我们将 \(\tt{Tree}\) 与 \(\tt{heap}\) (堆) 合并，

treap splay
0
Merkle Tree 简介

Merkle 树（Merkle Tree）是一种树状数据结构，通常用于验证大规模数据集的完整性和一致性。它的名字来源于其发明者 Ralph Merkle。Merkle 树在密码学、分布式系统和区块链等领域得到广泛应用，尤其在区块链中，它用于验证交易和区块的完整性，确保数据不被篡改。 下面是 Merk

merkle tree 简介
8
树的实例--模拟文件系统

博客地址：https://www.cnblogs.com/zylyehuo/ # -*- coding: utf-8 -*- class Node: # 链式存储 def __init__(self, name, type='dir'): self.name = name self.type = t

实例 模拟 文件系统
3
B+树要点梳理

B+树重要操作 中间节点 中间节点的key，与其对应的指针的原则是，小于key的元素在其指针指向的节点中 中间节点的key可以看成是右斜着排放的，即小于等于key的节点由key对应的指针指定，最有一个指针指向大于最右侧key的节点 分裂 当中间节点数量满了时，进行分裂，新生成一个相邻的中间节点rig

16
Windows 7操作系统全面解析与实用技巧

深入介绍Windows 7操作系统的基础知识、功能特性、分类和基本操作技巧，包括核心功能、特征、分类、安装方法、启动、文件管理、个性化设置等方面。旨在帮助用户深入理解Windows 7，并掌握提高工作效率和个性化设置的实用技巧。

windows
0
【知识点】浅入线段树与区间最值问题

线段树的数据结构、基本原理、构建方法、区间查询和更新操作，以及其在解决区间最值问题和进行优化（如懒标记）中的应用和代码实现。

5
小伙伴：我是专升本，能不写在简历里吗？

大家好，我是树哥。 最近我推出了简历辅导服务（详见：500 块就能获得 10 年的行业经验，太赚了！），有一位同学找我做了简历辅导。 在阅读他的简历的时候，我发现他的学历没有写入学时间和毕业时间，感觉不是很直观，于是让他补全一下。小伙伴回复说：我是专升本的，本科只有 2 年的时间，我担心写了之后就被

0
这款 AI 代码辅助插件真不错，还能帮你发现 bug！

大家好，我是树哥。 随着 ChatGPT 风靡全球之后，编程界也迎来了许多代码辅助工具，有非常出名的 Github Copilot 工具。今天，树哥给大家介绍一款免费的代码辅助插件，它无需代理上网，直接在 IDEA 中搜索安装即可。它不仅可以帮你辅助写代码，还可以帮你发现 bug 哦！它就是 ——

ai bug
1
# 热门排行
微软 New Bing AI 申请与使用保姆级教程（免魔法） ChatGPT API使用介绍 ChatGPT开发实战 一篇带你了解如何使用纯前端类Excel表格构建现金流量表 手把手教你玩转 Excel 数据透视表 为什么 C# 可能是最好的第一编程语言 .NET 入门到高级路线 提高工作效率的神器：基于前端表格实现Chrome Excel扩展插件 React + Springboot + Quartz，从0实现Excel报表自动化 用Echarts实现前端表格引用从属关系可视化
© PmDaddy. 2023 PmDaddy教程网 All rights reserved.