树链剖分

1.简介

这其实是一个很神奇的东西，分为三种，其中比较常见的是：重链剖分，长链剖分；

那么·这个用来解决什么问题呢？这个数据结构支持对于树上的·两个节点x，y，将其两点间的路径上的所有数加上一个值，并且可以查询 x到y的最短路上边的权值和。

3.相关概念

树链剖分：一种对树进行划分的算法，它先通过轻重边剖分将树分为多条链，保证每个点属于且只属于一条链，然后再通过数据结构（树状数组、BST、SPLAY、线段树等）来维护每一条链。

重儿子：一个结点的所有子树中，树的大小（即包括根结点的结点的个数）最大的子树之一的根结点（也就是当前结点的一个子节点），称为该节点的重儿子，注意，重儿子只能有1个，当出现

多个子树大小相同且都为最大时，我们随机选取其中一个作为重儿子，其他的则看做轻儿子。

轻儿子：一个结点的所有子结点中不是重儿子的结点

重链：一个结点与他的重儿子之间连的边

*注意，由于重儿子的定义，一棵树的重链剖分方式可能不唯一

3.树链剖分细节

为了对一棵树进行重链剖分，我们维护以下几个数组：

fa[x]:结点x的父亲

son[x]:结点x的重儿子

sz[x]:结点x的子树大小

dep[x]:结点x的深度

top[x]:结点x所在重链的顶点

seg[x]:结点x在线段树中的编号

rev[x]:线段树中结点x在原数组中的编号

用两个DFS对其进行维护

第一个dfs处理的是前4个数组

第二个dfs处理的是后3个数组

4.推荐例题

洛谷：P4315 月下“毛景树”

5.下面上代码：

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cmath>
  4 #include<cstring>
  5 #include<algorithm>
  6 #include<vector>
  7 #define N 100005
  8 
  9 using namespace std;
 10 
 11 vector<int > adj[N];
 12 int n,m,r,p,cnt=0;
 13 int son[N],deep[N],fa[N],size[N];
 14 int id[N],top[N],w[N];
 15 long long c1[N],c2[N];
 16 
 17 int lowbit(int x)
 18 {
 19     return x&(-x);
 20 }
 21 
 22 void add(int l,int r,int x)
 23 {
 24     x%=p;
 25     int ad1=(long long)(l-1)*x%p;
 26     int ad2=(long long)r*x%p;
 27     for(int t=l;t<=n;t+=lowbit(t))
 28     {
 29         c1[t]=(c1[t]+x)%p;
 30         c2[t]=(c2[t]+ad1)%p;
 31     }
 32     for(int t=r+1;t<=n;t+=lowbit(t))
 33     {
 34         c1[t]=(c1[t]-x)%p;
 35         c1[t]=(c1[t]+p)%p;
 36         c2[t]=(c2[t]-ad2)%p;
 37         c2[t]=(c2[t]+p)%p;
 38     }
 39     
 40 }
 41 
 42 int qwq(int i)
 43 {
 44     int res=0;
 45     for(int t=i;t>0;t-=lowbit(t))
 46     {
 47         res=(res+(long long )i*c1[t]%p)%p;
 48         res=(res-c2[t])%p;
 49         res=(res+p)%p;
 50     }
 51     return res;
 52 }
 53 
 54 int query(int l,int r)
 55 {
 56     int res=(qwq(r)-qwq(l-1))%p;
 57     return (res+p)%p;
 58 }
 59 //=======================================================================
 60  
 61 int  Read()
 62 {
 63     int num=0,k=1;
 64     char c=getchar();
 65     while(c!='-'&&(c<'0'||c>'9')) c=getchar();
 66     if(c=='-')
 67     {
 68         k=-1;
 69         c=getchar();
 70     }
 71     while(c>='0'&&c<='9') 
 72     {
 73         num=(num<<1)+(num<<3)+c-'0';
 74         c=getchar();
 75     }
 76     return num*k;
 77 }
 78 
 79 void print(int x)
 80 {
 81     if(x>9) print(x/10);
 82     putchar(x%10+'0');
 83 }
 84 
 85 void dfs1(int u,int f)
 86 {
 87     fa[u]=f;
 88     size[u]=1;
 89     deep[u]= deep[f]+1;
 90     int v,t=-1,l=adj[u].size();
 91     for(int i=0;i<l;++i)
 92     {
 93         v=adj[u][i];
 94         if(v==f) continue;
 95         dfs1(v,u);
 96         size[u]+=size[v];
 97         if(size[v]>t)
 98         {
 99             t=size[v];
100             son[u]=v;
101         }
102     }
103 }
104 
105 void dfs2(int u,int f)
106 {
107     top[u]=f;
108     id[u]=++cnt;
109     if(w[u]!=0) add(id[u],id[u],w[u]);
110     if(son[u]==0) return ;
111     dfs2(son[u],f);
112     int v,l=adj[u].size();
113     for(int i=0;i<l;++i)
114     {
115         v=adj[u][i];
116         if(v==son[u]||v==fa[u]) continue;
117         dfs2(v,v);
118     }
119 }
120 
121 int queryPath(int u,int v)
122 {
123     int res=0;
124     while(top[u]!=top[v])
125     {
126         if(deep[top[u]]<deep[top[v]]) swap(u,v);
127         res=(res+query(id[top[u]],id[u]))%p;
128         u=fa[top[u]];
129     }
130     if(deep[u]>deep[v]) swap(u,v);
131     res=(res+query(id[u],id[v]))%p;
132     return res;
133 }
134 
135 void addPath(int u,int v,int k) //路径上所有的点的权值加上k 
136 {
137     k%=p;
138     while(top[u]!=top[v])//倍增求lca 
139     {
140         if(deep[top[u]]<deep[top[v]]) swap(u,v);//保证u的链头的深度大于v的链头 
141         add(id[top[u]],id[u],k);//当前这一条链加k 
142         u=fa[top[u]];//进入下一条链 
143     }
144     if(deep[u]>deep[v]) swap(u,v);
145     add(id[u],id[v],k);
146 }
147 
148 int querySon(int u)
149 {
150     return query(id[u],id[u]+size[u]-1);
151 }
152 
153 void addSon(int u,int k)
154 {
155     k%=p;
156     add(id[u],id[u]+size[u]-1,k);
157 }
158 
159 int main ()
160 {
161     int u,v;
162     n=Read();
163     m=Read();
164     r=Read();
165     p=Read();
166     for(int i=1;i<=n;++i) w[i]=Read();
167     for(int i=1;i<n;++i)
168     {
169         u=Read();
170         v=Read();
171         adj[u].push_back(v);
172         adj[v].push_back(u);
173     }
174     dfs1(r,0);
175     dfs2(r,r);
176     int ans,op,x,y,z;
177     while(m--)
178     {
179         op=Read();
180         x=Read();
181         if(op==1)
182         {
183             y=Read();
184             z=Read();
185             addPath(x,y,z);
186             continue;
187         }
188         if(op==2)
189         {
190             y=Read();
191             ans=queryPath(x,y);
192             printf("%d
",ans);
193             continue;
194         }
195         if(op==3)
196         {
197             z=Read();
198             addSon(x,z);
199             continue;
200         }
201         ans = querySon(x);
202         printf("%d
",ans);
203     }
204     return 0;
205  }