用途

我想把一个本来是线性的东西放到树上做，维护路径或者是子树的各种性质，那就用树剖呗

它可以套线段树、树状数组、ST表（以及其他我不知道的）

做法

我们考虑把树分成一条条链，然后对每条链维护我们的数据结构（线段树等）。对于两点间路径的询问，只要把路径拆成好几条链统计答案就可以了

然后为了保证链数是$O(logn)$的，我们需要把每个点和他的重儿子连成一条链，所谓重儿子，就是节点数最多的儿子

所以做两遍dfs，第一遍求出节点的重儿子、父节点和深度（用于统计答案），第二遍按照重儿子优先的顺序去做dfs序，这样可以保证每条重链连续、而且每个子树连续

我们以这个dfs序为下标，建一棵线段树（或者别的什么）

再记每个链的最靠上的节点是谁，然后查询的时候一直拿着个往上跳就行了

所以每次操作$O(log^2n)$

例题

luogu4114 Qtree1（修改边权、查询路径最大边权）

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 #define LL long long int 9 #define inf 0x3f3f3f3f 10 using namespace std; 11 const int maxn=100010; 12 13 LL rd(){ 14 LL x=0;char c=getchar();int neg=1; 15 while(c<'0'||c>'9'){ if(c=='-') neg=-1;c=getchar();} 16 while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); 17 return x*neg; 18 } 19 20 struct Edge{ 21 int a,b,l,ne; 22 }eg[maxn*2]; 23 int N; 24 int egh[maxn],ect; 25 int wson[maxn],fa[maxn],dep[maxn]; 26 int val[maxn],num[maxn],root[maxn],top[maxn],het[maxn]; 27 int ch[maxn*3][2],v[maxn*4],pct; 28 29 inline void adeg(int a,int b,int l){ 30 eg[ect].a=a;eg[ect].b=b;eg[ect].l=l;eg[ect].ne=egh[a];egh[a]=ect++; 31 } 32 33 int dfs1(int x,int f){ 34 int ma=-inf,mi=0,re=1;fa[x]=f;dep[x]=dep[f]+1; 35 for(int i=egh[x];i!=-1;i=eg[i].ne){ 36 int b=eg[i].b;if(b==f) continue; 37 int c=dfs1(b,x);re+=c; 38 val[b]=max(val[b],eg[i].l); 39 if(c>ma) ma=c,mi=b; 40 }wson[x]=mi;return re; 41 } 42 43 inline void update(int p){v[p]=max(v[ch[p][0]],v[ch[p][1]]);} 44 45 void build(int &p,int l,int r){ 46 p=++pct;if(l==r) v[p]=val[num[l]]; 47 else{ 48 int m=l+r>>1; 49 build(ch[p][0],l,m);build(ch[p][1],m+1,r); 50 update(p); 51 } 52 } 53 void change(int p,int l,int r,int x,int y){ 54 if(l==r) v[p]=y; 55 else{ 56 int m=l+r>>1; 57 if(x<=m) change(ch[p][0],l,m,x,y); 58 else change(ch[p][1],m+1,r,x,y); 59 update(p); 60 } 61 } 62 int query(int p,int l,int r,int x,int y){ 63 if(x<=l&&r<=y) return v[p]; 64 else{ 65 int m=l+r>>1,re=-inf; 66 if(x<=m) re=max(re,query(ch[p][0],l,m,x,y)); 67 if(y>=m+1) re=max(re,query(ch[p][1],m+1,r,x,y)); 68 return re; 69 } 70 } 71 72 void dfs2(int x,int f){ 73 if(wson[f]!=x){ int i,j; 74 for(i=1,j=x;j;j=wson[j],i++) num[i]=j,top[j]=x; 75 het[x]=i-1;build(root[x],1,het[x]); 76 }for(int i=egh[x];i!=-1;i=eg[i].ne){ 77 int b=eg[i].b;if(b==f) continue; 78 dfs2(b,x); 79 } 80 } 81 82 void solveC(int a,int b){ 83 int x=eg[a*2-1].a,y=eg[a*2-1].b; 84 if(dep[x]
             
              dep[y]) swap(x,y); 96 return max(re,query(root[top[x]],1,het[top[x]],dep[x]-dep[top[x]]+2,dep[y]-dep[top[x]]+1)); 97 } 98 99 int main(){100 //freopen("4114.in","r",stdin);101 int i,j,k;102 char s[20];103 N=rd();memset(egh,-1,sizeof(egh));104 for(i=1;i
             
            
           
          
         
        
       
      

(改路径/子树点权 查路径/子树点权和/最大值)

1 #include
      
         2 #define pa pair
       
          3 #define CLR(a,x) memset(a,x,sizeof(a))  4 using namespace std;  5 typedef long long ll;  6 const int maxs=2e7,maxn=1e6+5,QS=233333333,QM=114514810;  7   8 inline char gc(){  9     static char buf[maxs],*p1=buf,*p2=buf; 10     return p1==p2&&(p2=(p1=buf)+fread(buf,1,maxs,stdin),p1==p2)?EOF:*p1++; 11 } 12  13 inline ll rd(){ 14     ll x=0;char c=gc();int neg=1; 15     while(c<'0'||c>'9'){
    if(c=='-') neg=-1;c=gc();} 16     while(c>='0'&&c<='9') x=x*10+c-'0',c=gc(); 17     return x*neg; 18 } 19  20 int eg[maxn*2][2],egh[maxn],ect; 21 int N,M,root,fa[maxn]; 22 int dep[maxn],wson[maxn],dfn[maxn][2],top[maxn],siz[maxn]; 23 int ch[maxn*4][2],tot,id[maxn]; 24 int pct; 25 ll sum[maxn*4],ma[maxn*4],laz[maxn*4]; 26 int v[maxn]; 27  28 inline void adeg(int a,int b){ 29     eg[++ect][0]=b;eg[ect][1]=egh[a];egh[a]=ect; 30 } 31  32 inline void update(int p){ 33     if(!ch[p][0]) return; 34     sum[p]=sum[ch[p][0]]+sum[ch[p][1]]; 35     ma[p]=max(ma[ch[p][0]],ma[ch[p][1]]); 36 } 37  38 void build(int &p,int l,int r){ 39     if(!p) p=++pct; 40     if(l==r) sum[p]=ma[p]=v[id[l]]; 41     else{ 42         int m=l+r>>1; 43         build(ch[p][0],l,m);build(ch[p][1],m+1,r); 44         update(p); 45     } 46 } 47  48 inline void pushdown(int p,int l,int r){ 49     if(!laz[p]) return; 50     if(l
        
         >1; 53         laz[a]+=laz[p]; 54         sum[a]+=(m-l+1)*laz[p]; 55         ma[a]+=laz[p]; 56          57         laz[b]+=laz[p]; 58         sum[b]+=(r-m)*laz[p]; 59         ma[b]+=laz[p]; 60     }laz[p]=0; 61 } 62  63 void add(int p,int l,int r,int x,int y,int z){ 64     if(x<=l&&r<=y){ 65         laz[p]+=z; 66         sum[p]+=(r-l+1)*z; 67         ma[p]+=z; 68     }else{ 69         pushdown(p,l,r); 70         int m=l+r>>1; 71         if(x<=m) add(ch[p][0],l,m,x,y,z); 72         if(y>=m+1) add(ch[p][1],m+1,r,x,y,z); 73         update(p); 74     } 75 } 76  77 ll querys(int p,int l,int r,int x,int y){ 78     pushdown(p,l,r); 79     if(x<=l&&r<=y){ 80         return sum[p]; 81     }else{ 82         int m=l+r>>1;ll re=0; 83         if(x<=m) re=querys(ch[p][0],l,m,x,y); 84         if(y>=m+1) re+=querys(ch[p][1],m+1,r,x,y); 85         return re; 86     } 87 } 88  89 void querym(int p,int l,int r,int x,int y,ll &re){ 90     pushdown(p,l,r); 91     if(x<=l&&r<=y){ 92         re=max(re,ma[p]); 93     }else{ 94         int m=l+r>>1; 95         if(x<=m&&ma[ch[p][0]]>re) querym(ch[p][0],l,m,x,y,re); 96         if(y>=m+1&&ma[ch[p][1]]>re) querym(ch[p][1],m+1,r,x,y,re); 97     } 98 } 99 100 void dfs1(int x){101     siz[x]=1;102     int m=0;103     for(int i=egh[x];i;i=eg[i][1]){104         int b=eg[i][0];if(b==fa[x]) continue;105         dep[b]=dep[x]+1;106         fa[b]=x;107         dfs1(b);108         siz[x]+=siz[b];109         if(siz[b]>m) m=siz[b],wson[x]=b;110     }111 }112 113 void dfs2(int x){114     if(x==wson[fa[x]]) top[x]=top[fa[x]];115     else top[x]=x;116     dfn[x][0]=++tot;id[tot]=x;117     if(wson[x]) dfs2(wson[x]);118     for(int i=egh[x];i;i=eg[i][1]){119         int b=eg[i][0];if(b==fa[x]||b==wson[x]) continue;120         dfs2(b);121     }122     dfn[x][1]=tot;123 }124 125 ll solve(int x,int y,int op){126     ll re=(op==QM?-1e11:0);127     while(top[x]!=top[y]){128         if(dep[top[x]]