树链剖分
树链剖分听起来超级难，然而昨天听说我们这一届有同学已经会了，感觉压力很大。去看了一下所谓“树剖的前置知识”，惊奇的发现自己都会！于是莫名其妙的又学起了数据结构...noip前除了这个我就再不学超纲内容了...
树链剖分：开始，有一个序列，要区间修改查询，于是有了线段树。后来，这个序列长成了一棵树，要路径修改查询、子树修改查询，于是有了树链剖分。
找了好几个课件，然而还是看不懂，决定先在博客上理理思路再写。
把一棵树切成多条链，就可以降低树上操作的复杂度了。但是怎么切比较好呢？按照一种的轻重链剖分的思想。以下是一些定义：
重儿子：对于每一个非叶子节点，它的子节点中子树节点最多的节点为该节点的重儿子；
轻儿子：对于每一个非叶子节点，它的儿子中非重儿子的儿子即为轻儿子；
重边：连接两个重儿子的边叫做重边；
轻边：不是重边的边；
重链：相邻重边连起来的链叫重链；
叶子节点，如果是轻儿子，则有一条以自己为起点的长度为1的链；
重链以轻儿子为起点；
第一次dfs：求取每一个节点的子树大小，深度，重儿子，父亲；
第二次dfs：按照树的dfs序进行重新编号，给新编号赋初始值，处理每一个点所在链的顶端，处理每一条链。dfs的顺序要按照先重儿子后轻儿子的顺序，这样每条重链中的点在dfs序中是连续的。还有就是每个子树的编号也是连续的。
如果正常的话现在大概已经开了7~8个数组了...
于是就剖分完啦，现在来看看洛谷的树剖模板：
1.$x$到$y$的路径上每个点点权加$z$；
2.询问$x$,$y$路径上的点权和；
3.以$x$为根的子树内点权全部加$z$；
4.询问以$x$为根的子树的点权和。
因为路径、子树现在都是连续的，于是就成了区间加，区间求和。用线段树。
（插播一条新闻：在写下这句话之前，我刚刚过掉洛谷模板，所以之前说的话不保证对，下面说的话至少保证能过模板）
其实到这里也就没什么东西了，路径点权求和和修改差不多，不停对不在同一条重链上的，链的初始位置更深的链进行求和，直到两点汇于一条链。
子树就更简单啦，直接用子树节点个数加上根的新ID-1就是子树。
[模板]树链剖分:https://www.luogu.org/problemnew/show/P3384
1 # include <cstdio> 2 # include <iostream> 3 # define R register int 4 # define nl n<<1 5 # define nr n<<1|1 6 7 using namespace std; 8 9 const int maxn=100005; 10 int rx,rf,h=0,n,m,r,p,x,y,z,coun=0; 11 int A[maxn],firs[maxn<<1],nid[maxn]; 12 int F[maxn],dep[maxn],siz[maxn],son[maxn],Top[maxn]; 13 int a[maxn]; 14 int t[maxn<<2],delta[maxn<<2]; 15 char rc; 16 17 inline int read() 18 { 19 rx=0,rf=1; 20 rc=getchar(); 21 while (!isdigit(rc)) 22 { 23 if(rc=='-') rf=-rf; 24 rc=getchar(); 25 } 26 while (isdigit(rc)) 27 { 28 rx=(rx<<3)+(rx<<1)+(rc^48); 29 rc=getchar(); 30 } 31 return rx*rf; 32 } 33 34 struct edge 35 { 36 int nex,too; 37 }g[maxn<<1]; 38 39 void add_edge(int x,int y) 40 { 41 g[++h].too=y; 42 g[h].nex=firs[x]; 43 firs[x]=h; 44 } 45 46 void dfs1(int roo) 47 { 48 siz[roo]=1; 49 int j,maxs=-1; 50 for (R i=firs[roo];i;i=g[i].nex) 51 { 52 j=g[i].too; 53 if(dep[j]) continue; 54 F[j]=roo; 55 dep[j]=dep[roo]+1; 56 dfs1(j); 57 siz[roo]+=siz[j]; 58 if(siz[j]>maxs) 59 { 60 maxs=siz[j]; 61 son[roo]=j; 62 } 63 } 64 return ; 65 } 66 67 void dfs2(int x,int Tp) 68 { 69 nid[x]=++coun; 70 a[coun]=A[x]; 71 Top[x]=Tp; 72 if(!son[x]) return; 73 dfs2(son[x],Tp); 74 int j; 75 for (R i=firs[x];i;i=g[i].nex) 76 { 77 j=g[i].too; 78 if(j==F[x]||j==son[x]) continue; 79 dfs2(j,j); 80 } 81 return ; 82 } 83 84 inline void pushdown(int n,int l,int r) 85 { 86 int mid=(l+r)>>1,x=delta[n]; 87 delta[nl]+=x; 88 delta[nr]+=x; 89 delta[n]=0; 90 t[nl]=(t[nl]+(mid-l+1)*x)%p; 91 t[nr]=(t[nr]+(r-mid)*x)%p; 92 return ; 93 } 94 95 inline void add(int n,int l,int r,int ll,int rr,int z) 96 { 97 if(ll<=l&&r<=rr) 98 { 99 delta[n]=(delta[n]+z)%p; 100 t[n]=(t[n]+(r-l+1)*z%p)%p; 101 return ; 102 } 103 int mid=(l+r)>>1; 104 if(delta[n]) pushdown(n,l,r); 105 if(ll<=mid) add(nl,l,mid,ll,rr,z); 106 if(rr>mid) add(nr,mid+1,r,ll,rr,z); 107 t[n]=(t[nl]+t[nr])%p; 108 return ; 109 } 110 111 inline int ask(int n,int l,int r,int ll,int rr) 112 { 113 if(ll<=l&&r<=rr) 114 return t[n]; 115 int mid=(l+r)>>1,ans=0; 116 if(delta[n]) pushdown(n,l,r); 117 if(ll<=mid) ans=(ans+ask(nl,l,mid,ll,rr))%p; 118 if(rr>mid) ans=(ans+ask(nr,mid+1,r,ll,rr))%p; 119 return ans; 120 } 121 122 inline int ask1(int x,int y) 123 { 124 int ans=0; 125 while (Top[x]!=Top[y]) 126 { 127 if(dep[ Top[x] ]<dep[ Top[y] ]) swap(x,y); 128 ans=(ans+ask(1,1,n,nid[Top[x]],nid[x]))%p; 129 x=F[ Top[x] ]; 130 } 131 if(dep[x]>dep[y]) swap(x,y); 132 ans=(ans+ask(1,1,n,nid[x],nid[y]))%p; 133 return ans; 134 } 135 136 inline void add1(int x,int y,int z) 137 { 138 z=z%p; 139 while (Top[x]!=Top[y]) 140 { 141 if(dep[ Top[x] ]<dep[ Top[y] ]) swap(x,y); 142 add(1,1,n,nid[ Top[x] ],nid[x],z); 143 x=F[ Top[x] ]; 144 } 145 if(dep[x]>dep[y]) swap(x,y); 146 add(1,1,n,nid[x],nid[y],z); 147 } 148 149 inline int ask2(int x) 150 { 151 return ask(1,1,n,nid[x],nid[x]+siz[x]-1)%p; 152 } 153 154 inline void add2(int x,int z) 155 { 156 add(1,1,n,nid[x],nid[x]+siz[x]-1,z); 157 } 158 159 inline void build(int n,int l,int r) 160 { 161 if(l==r) 162 { 163 t[n]=a[l]%p; 164 return; 165 } 166 int mid=(l+r)>>1; 167 build(nl,l,mid); 168 build(nr,mid+1,r); 169 t[n]=(t[nl]+t[nr])%p; 170 } 171 172 int main() 173 { 174 n=read(),m=read(),r=read(),p=read(); 175 for (R i=1;i<=n;++i) 176 A[i]=read(); 177 for (R i=1;i<n;++i) 178 { 179 x=read(); 180 y=read(); 181 add_edge(x,y); 182 add_edge(y,x); 183 } 184 dep[r]=1; 185 dfs1(r); 186 dfs2(r,r); 187 build(1,1,n); 188 int op; 189 for (R i=1;i<=m;++i) 190 { 191 op=read(); 192 if(op==1) 193 { 194 x=read(),y=read(),z=read(); 195 add1(x,y,z); 196 } 197 if(op==2) 198 { 199 x=read(),y=read(); 200 printf("%d\n",ask1(x,y)); 201 } 202 if(op==3) 203 { 204 x=read(),z=read(); 205 add2(x,z); 206 } 207 if(op==4) 208 { 209 x=read(); 210 printf("%d\n",ask2(x)); 211 } 212 } 213 return 0; 214 }
树链剖分写起来很长，而且开了很多的数组，所以有一个必须注意的问题就是不要弄混了，下面是一些注意事项：
1.如果一开始已经有点权，别忘了初始化线段树。因为线段树是为了后面的链剖准备的，里面的节点编号应该是新编的ID，所以要在两个$dfs$之后再初始化；
2.如果出错了就一个函数一个函数的检查，因为比较复杂，不是很适合调试，所以仔细看，尤其是觉得不会错的地方一定不要放过。譬如我第一次做的时候就是把线段树的$pushdown$写错了；
3.多看几个资料，别学成假的树剖了...比如重儿子的定义是子树大小最大，不是儿子数最大。发现好多资料都说的语焉不详，欺骗无知OIer。所以说一定要看代码！
4.调试的时候构造数据，注意$ID[x]$不要正好等于$x$；
2018.6.23：再过两个小时就要发中考成绩了！甚至感觉无心学习，不如敲个树剖板子虚度一下光阴，毕竟刚学完，$2h$还不一定够呢...接到新的通知,说18:00才发成绩啊...
中考成绩发了，然而我没有做出来那道题...很奇妙，现在感觉中考成绩一点也不重要了，甚至不如树剖的一道题。
[ZJOI2008]树的统计：https://www.luogu.org/problemnew/show/P2590
题意概述：在一棵树上，支持路径求最大值，求和，单点修改。
模板中的模板，但是得了5次20分，究其原因：每次交的都是同一个...只是在对拍的$my.cpp$里改了，交的却是$lg2590$...
注意：查询时直接查询$x$,$y$；修改时是直接修改的线段树上的点，是按照新的$ID$建的树，所以要传进$id[x]$;
1 # include <iostream> 2 # include <cstdio> 3 # include <cstring> 4 # include <string> 5 # define R register int 6 # define nl n<<1 7 # define nr n<<1|1 8 9 using namespace std; 10 11 const int maxn=30005; 12 int h=0,n,q; 13 int ra,rb,rx,rf; 14 char rc; 15 int coun=0,dep[maxn],Top[maxn],A[maxn],firs[maxn],siz[maxn],son[maxn],F[maxn],id[maxn],a[maxn],tm[maxn<<2]; 16 long long ts[maxn<<2]; 17 struct edge 18 { 19 int nex,too; 20 }g[maxn<<1]; 21 22 inline int read() 23 { 24 rx=0,rf=1; 25 rc=getchar(); 26 while (!isdigit(rc)) 27 { 28 if(rc=='-') rf=-rf; 29 rc=getchar(); 30 } 31 while (isdigit(rc)) 32 { 33 rx=(rx<<3)+(rx<<1)+(rc^48); 34 rc=getchar(); 35 } 36 return rx*rf; 37 } 38 39 inline void dfs1(int roo) 40 { 41 siz[roo]=1; 42 int j,Maxx=-1; 43 for (R i=firs[roo];i;i=g[i].nex) 44 { 45 j=g[i].too; 46 if(dep[j]) continue; 47 dep[j]=dep[roo]+1; 48 F[j]=roo; 49 dfs1(j); 50 siz[roo]+=siz[j]; 51 if(siz[j]>Maxx) 52 { 53 Maxx=siz[j]; 54 son[roo]=j; 55 } 56 } 57 return ; 58 } 59 60 inline void dfs2(int x,int Tp) 61 { 62 int j; 63 Top[x]=Tp; 64 id[x]=++coun; 65 a[coun]=A[x]; 66 if(!son[x]) return ; 67 dfs2(son[x],Tp); 68 for (R i=firs[x];i;i=g[i].nex) 69 { 70 j=g[i].too; 71 if(j==F[x]||j==son[x]) continue; 72 dfs2(j,j); 73 } 74 return ; 75 } 76 77 inline void build(int n,int l,int r) 78 { 79 if(l==r) 80 { 81 tm[n]=ts[n]=a[l]; 82 return ; 83 } 84 int mid=(l+r)>>1; 85 build(nl,l,mid); 86 build(nr,mid+1,r); 87 ts[n]=ts[nl]+ts[nr]; 88 tm[n]=max(tm[nl],tm[nr]); 89 } 90 91 inline void add(int a,int b) 92 { 93 g[++h].too=b; 94 g[h].nex=firs[a]; 95 firs[a]=h; 96 } 97 98 inline void change(int n,int l,int r,int pos,int v) 99 { 100 if(l==r) 101 { 102 tm[n]=ts[n]=v; 103 return ; 104 } 105 int mid=(l+r)>>1; 106 if(pos<=mid) change(nl,l,mid,pos,v); 107 if(pos>mid) change(nr,mid+1,r,pos,v); 108 tm[n]=max(tm[nl],tm[nr]); 109 ts[n]=ts[nl]+ts[nr]; 110 return ; 111 } 112 113 inline long long asks(int n,int l,int r,int ll,int rr) 114 { 115 if(ll<=l&&r<=rr) 116 return ts[n]; 117 int mid=(l+r)>>1; 118 long long ans=0; 119 if(ll<=mid) ans+=asks(nl,l,mid,ll,rr); 120 if(rr>mid) ans+=asks(nr,mid+1,r,ll,rr); 121 return ans; 122 } 123 124 inline int askm(int n,int l,int r,int ll,int rr) 125 { 126 if(ll<=l&&r<=rr) 127 return tm[n]; 128 int mid=(l+r)>>1; 129 int ans=-999999; 130 if(ll<=mid) ans=max(ans,askm(nl,l,mid,ll,rr)); 131 if(rr>mid) ans=max(ans,askm(nr,mid+1,r,ll,rr)); 132 return ans; 133 } 134 135 inline long long ask_sum(int x,int y) 136 { 137 long long ans=0; 138 while (Top[x]!=Top[y]) 139 { 140 if(dep[ Top[x] ]<dep[ Top[y] ]) swap(x,y); 141 ans+=asks(1,1,n,id[ Top[x] ],id[x]); 142 x=F[ Top[x] ]; 143 } 144 if(dep[x]>dep[y]) swap(x,y); 145 ans+=asks(1,1,n,id[x],id[y]); 146 return ans; 147 } 148 149 inline int ask_max(int x,int y) 150 { 151 int ans=-30009; 152 while (Top[x]!=Top[y]) 153 { 154 if(dep[ Top[x] ]<dep[ Top[y] ]) swap(x,y); 155 ans=max(ans,askm(1,1,n,id[ Top[x] ],id[x])); 156 x=F[ Top[x] ]; 157 } 158 if(dep[x]>dep[y]) swap(x,y); 159 ans=max(ans,askm(1,1,n,id[x],id[y])); 160 return ans; 161 } 162 163 int main() 164 { 165 n=read(); 166 for (int i=1;i<n;i++) 167 { 168 ra=read(); 169 rb=read(); 170 add(ra,rb); 171 add(rb,ra); 172 } 173 for (int i=1;i<=n;i++) 174 A[i]=read(); 175 dep[1]=1; 176 dfs1(1); 177 dfs2(1,1); 178 build(1,1,n); 179 q=read(); 180 string op; 181 int x,y; 182 while (q--) 183 { 184 cin>>op; 185 x=read(); 186 y=read(); 187 if(op=="CHANGE") change(1,1,n,id[x],y); 188 if(op=="QMAX") printf("%d\n",ask_max(x,y)); 189 if(op=="QSUM") printf("%lld\n",ask_sum(x,y)); 190 } 191 return 0; 192 }
[SHOI2012]魔法树：https://www.luogu.org/problemnew/show/P3833
题意概述：区间加，子树求和。
竟然又是一个模板题，原来去某夏令营的时候听说每个模板至少敲五遍才能记住，那今天写完这个题，明天后天再各写一个类模板题，再往后找一点配合树链剖分的非模板题做一做。
# include <cstdio> # include <iostream> # define R register int # define nl n<<1 # define nr n<<1|1 using namespace std; const int maxn=100009; struct edge { int nex,too; }g[maxn<<1]; char rc,op; int h,coun,d,rx,rf,u,v,n,q,F[maxn],son[maxn],id[maxn],dep[maxn],siz[maxn],Top[maxn],firs[maxn]; long long c[maxn<<2],delta[maxn<<2]; inline int read() { rx=0,rf=1; rc=getchar(); while (!isdigit(rc)) { if(rc=='-') rf=-rf; rc=getchar(); } while (isdigit(rc)) { rx=(rx<<3)+(rx<<1)+(rc^48); rc=getchar(); } return rx*rf; } inline void dfs1(int roo) { siz[roo]=1; int j,maxs=-1; for (R i=firs[roo];i;i=g[i].nex) { j=g[i].too; if(dep[j]) continue; dep[j]=dep[roo]+1; F[j]=roo; dfs1(j); siz[roo]+=siz[j]; if(siz[j]>maxs) { maxs=siz[j]; son[roo]=j; } } return ; } inline void dfs2(int x,int Tp) { int j; Top[x]=Tp; id[x]=++coun; if(!son[x]) return ; dfs2(son[x],Tp); for (R i=firs[x];i;i=g[i].nex) { j=g[i].too; if(j==F[x]||j==son[x]) continue; dfs2(j,j); } return ; } inline void pushdown(int n,int l,int r) { long long x=delta[n]; int mid=(l+r)>>1; delta[n]=0; delta[nl]+=x; delta[nr]+=x; c[nl]+=(mid-l+1)*x; c[nr]+=(r-mid)*x; return ; } inline void add(int n,int l,int r,int ll,int rr,int v) { if(ll<=l&&r<=rr) { delta[n]+=v; c[n]+=(r-l+1)*v; return ; } int mid=(l+r)>>1; if(delta[n]) pushdown(n,l,r); if(ll<=mid) add(nl,l,mid,ll,rr,v); if(rr> mid) add(nr,mid+1,r,ll,rr,v); c[n]=c[nl]+c[nr]; return ; } inline long long ask(int n,int l,int r,int ll,int rr) { if(ll<=l&&r<=rr) { return c[n]; } int mid=(l+r)>>1; long long ans=0; if(delta[n]) pushdown(n,l,r); if(ll<=mid) ans+=ask(nl,l,mid,ll,rr); if(rr>mid) ans+=ask(nr,mid+1,r,ll,rr); return ans; } inline void add_l(int x,int y,int d) { while (Top[x]!=Top[y]) { if(dep[ Top[x] ]<dep[ Top[y] ]) swap(x,y); add(1,1,n,id[ Top[x] ],id[x],d); x=F[ Top[x] ]; } if(dep[x]>dep[y]) swap(x,y); add(1,1,n,id[x],id[y],d); return ; } inline long long ask_s(int x) { return ask(1,1,n,id[x],id[x]+siz[x]-1); } inline void add_edge(int x,int y) { g[++h].too=y; g[h].nex=firs[x]; firs[x]=h; } int main() { scanf("%d",&n); for (R i=1;i<n;++i) { u=read(),v=read(); add_edge(u,v),add_edge(v,u); } dep[0]=1; dfs1(0); dfs2(0,0); scanf("%d",&q); while (q--) { cin>>op; if(op=='A') { u=read(),v=read(),d=read(); add_l(u,v,d); } else { u=read(); printf("%lld\n",ask_s(u)); } } return 0; }
染色:https://www.lydsy.com/JudgeOnline/problem.php?id=2243
题意概述:给定一棵无根树,支持路径染色,路径查询有多少"段"颜色.$n<=10^5$
什么是一"段"颜色,就是极长的一段相同颜色.
如果是序列上的问题，可以通过线段树记录区间答案，左右端点颜色来快速的做，但是到树上...树剖就好了呀。这里要注意分别保存两个起点目前最高处的颜色，如果有时要交换两个端点，那么这个也要换，等到最后一次查询时两个端点都要检查一下是否和旁边的合成了一段。然后...别忘了pushdown...估计除了我也没人会忘了...
1 # include <cstdio> 2 # include <iostream> 3 # include <cstring> 4 # include <string> 5 # include <algorithm> 6 # include <cmath> 7 # define R register int 8 # define nl (n<<1) 9 # define nr (n<<1|1) 10 11 using namespace std; 12 13 const int maxn=100005; 14 int n,m,c[maxn],x,y,h,firs[maxn],dep[maxn],id[maxn],f[maxn],son[maxn],siz[maxn],top[maxn],cnt,a[maxn],col; 15 char st[5]; 16 struct node 17 { 18 int l,r,ans,delta; 19 }t[maxn<<2]; 20 struct edge 21 { 22 int too,nex; 23 }g[maxn<<1]; 24 25 int read() 26 { 27 R x=0; 28 char c=getchar(); 29 while(!isdigit(c)) c=getchar(); 30 while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar(); 31 return x; 32 } 33 34 void add (int x,int y) 35 { 36 g[++h].nex=firs[x]; 37 firs[x]=h; 38 g[h].too=y; 39 } 40 41 void dfs1 (int x) 42 { 43 int j,maxx=0; 44 siz[x]=1; 45 for (R i=firs[x];i;i=g[i].nex) 46 { 47 j=g[i].too; 48 if(dep[j]) continue; 49 dep[j]=dep[x]+1; 50 f[j]=x; 51 dfs1(j); 52 siz[x]+=siz[j]; 53 if(siz[j]>maxx) maxx=siz[j],son[x]=j; 54 } 55 } 56 57 void dfs2 (int x,int Tp) 58 { 59 int j; 60 id[x]=++cnt; 61 a[cnt]=c[x]; 62 top[x]=Tp; 63 if(!son[x]) return; 64 dfs2(son[x],Tp); 65 for (R i=firs[x];i;i=g[i].nex) 66 { 67 j=g[i].too; 68 if(j==son[x]||j==f[x]) continue; 69 dfs2(j,j); 70 } 71 } 72 73 node update (node a,node b) 74 { 75 node x; 76 x.ans=a.ans+b.ans; 77 if(a.r==b.l) x.ans--; 78 x.l=a.l; 79 x.r=b.r; 80 x.delta=-1; 81 return x; 82 } 83 84 void pushdown (int n) 85 { 86 int x=t[n].delta; 87 t[nl].l=t[nr].l=t[nl].r=t[nr].r=x; 88 t[nl].delta=t[nr].delta=x; 89 t[n].delta=-1; 90 t[nl].ans=t[nr].ans=1; 91 } 92 93 void build (int n,int l,int r) 94 { 95 if(l==r) 96 { 97 t[n].ans=1; 98 t[n].l=t[n].r=a[l]; 99 t[n].delta=-1; 100 return; 101 } 102 int mid=(l+r)>>1; 103 build(nl,l,mid); 104 build(nr,mid+1,r); 105 t[n]=update(t[nl],t[nr]); 106 t[n].delta=-1; 107 } 108 109 void chan (int n,int l,int r,int ll,int rr,int col) 110 { 111 if(ll<=l&&r<=rr) 112 { 113 t[n].ans=1; 114 t[n].l=t[n].r=col; 115 t[n].delta=col; 116 return; 117 } 118 int mid=(l+r)>>1; 119 if(t[n].delta!=-1) pushdown(n); 120 if(ll<=mid) chan(nl,l,mid,ll,rr,col); 121 if(rr>mid) chan(nr,mid+1,r,ll,rr,col); 122 t[n]=update(t[nl],t[nr]); 123 } 124 125 node ask (int n,int l,int r,int ll,int rr) 126 { 127 if(ll<=l&&r<=rr) return t[n]; 128 int mid=(l+r)>>1; 129 if(t[n].delta!=-1) pushdown(n); 130 if(rr<=mid) return ask(nl,l,mid,ll,rr); 131 if(ll>mid) return ask(nr,mid+1,r,ll,rr); 132 return update(ask(nl,l,mid,ll,rr),ask(nr,mid+1,r,ll,rr)); 133 } 134 135 int ask_link (int x,int y) 136 { 137 node t; 138 int colx=-1,coly=-1,ans=0; 139 while(top[x]!=top[y]) 140 { 141 if(dep[ top[x] ]<dep[ top[y] ]) swap(x,y),swap(colx,coly); 142 t=ask(1,1,n,id[ top[x] ],id[x]); 143 if(t.r==colx) ans+=t.ans-1; 144 else ans+=t.ans; 145 colx=t.l; 146 x=f[ top[x] ]; 147 } 148 if(dep[x]>dep[y]) swap(x,y),swap(colx,coly); 149 t=ask(1,1,n,id[x],id[y]); 150 ans+=t.ans; 151 if(t.l==colx) ans--; 152 if(t.r==coly) ans--; 153 return ans; 154 } 155 156 void cov (int x,int y,int col) 157 { 158 while(top[x]!=top[y]) 159 { 160 if(dep[ top[x] ]<dep[ top[y] ]) swap(x,y); 161 chan(1,1,n,id[ top[x] ],id[x],col); 162 x=f[ top[x] ]; 163 } 164 if(dep[x]>dep[y]) swap(x,y); 165 chan(1,1,n,id[x],id[y],col); 166 } 167 168 int main() 169 { 170 n=read(),m=read(); 171 for (R i=1;i<=n;++i) c[i]=read(); 172 for (R i=1;i<n;++i) 173 { 174 x=read(),y=read(); 175 add(x,y); 176 add(y,x); 177 } 178 dep[1]=1; 179 dfs1(1); 180 dfs2(1,1); 181 build(1,1,n); 182 for (R i=1;i<=m;++i) 183 { 184 scanf("%s",st); 185 if(st[0]=='C') 186 { 187 x=read(),y=read(),col=read(); 188 cov(x,y,col); 189 } 190 else 191 { 192 x=read(),y=read(); 193 printf("%d\n",ask_link(x,y)); 194 } 195 } 196 return 0; 197 }
以下就是手残选手的一些心得，手不残的同学就不用往下看了...没再有题了。
从零开始写链剖：
首先先读入边，点权。如果给定了根，一定要用它给的根，如果没有，看看编号从几开始，选择最小编号作为根。先给根的深度赋值为$1$，然后进行两次dfs。先用语言叙述一下，为了防止手残的进一步发展，再贴上这块代码。在第一遍$dfs$中，先将当前的点的子树和赋为1（自己），定义一个变量保存目前这个节点的儿子中子树和最多的，可以先赋值为-1，遍历邻接表。如果遍历到深度为$0$的点，就认为是这个根的儿子并进行赋值($dep[j]=dep[roo]+1$)，$roo$自然就成为了$F[j]$，别忘了赋值；接下来以$j$为根接着遍历下去，完成后判断是否为最大的子树，如果是,就$son[roo]=j,maxs=siz[j]$；
1 void dfs1(int roo) 2 { 3 siz[roo]=1; 4 int j,maxs=-1; 5 for (R i=firs[roo];i;i=g[i].nex) 6 { 7 j=g[i].too; 8 if(dep[j]) continue; 9 F[j]=roo; 10 dep[j]=dep[roo]+1; 11 dfs1(j); 12 siz[roo]+=siz[j]; 13 if(siz[j]>maxs) 14 { 15 maxs=siz[j]; 16 son[roo]=j; 17 } 18 } 19 return ; 20 }
$dfs_2$中，传入的是$(roo,roo)$，进入时，给当前的$roo$赋值$ID$，如果有读入的点权，就赋值给新的$ID$的权值数组。如果是叶子，就可以$return$了，然后赋值$Top$,对于重儿子接着递归$dfs_2(son[x],Tp)$；循环给其他儿子加链，循环时排除父亲和重儿子，$dfs_2(j,j)$。
1 void dfs2(int x,int Tp) 2 { 3 nid[x]=++coun; 4 a[coun]=A[x]; 5 Top[x]=Tp; 6 if(!son[x]) return; 7 dfs2(son[x],Tp); 8 int j; 9 for (R i=firs[x];i;i=g[i].nex) 10 { 11 j=g[i].too; 12 if(j==F[x]||j==son[x]) continue; 13 dfs2(j,j); 14 } 15 return ; 16 }
这样两个$dfs$就写完了，对于新的权值数组建树，线段树相关操作能别再错了吗...每当区间分开成两半进行查询之前别忘了清空$delta$标记，建树以及区间加完了别忘记$update$。
现在就只剩修改查询了，还是比较轻松愉快的。
修改和查询几乎一模一样，首先从子树修改开始看：
1 inline void add2(int x,int z) 2 { 3 add(1,1,n,nid[x],nid[x]+siz[x]-1,z); 4 }
非常简单吧，注意这里传进来的x应该是原数组的下表，而不是新的$ID$。
加上一个子树查询：
1 inline int ask2(int x) 2 { 3 return ask(1,1,n,nid[x],nid[x]+siz[x]-1)%p; 4 }
然后是稍微复杂的路径修改查询：
1 inline int ask1(int x,int y) 2 { 3 int ans=0; 4 while (Top[x]!=Top[y]) 5 { 6 if(dep[ Top[x] ]<dep[ Top[y] ]) swap(x,y); 7 ans=(ans+ask(1,1,n,nid[Top[x]],nid[x]))%p; 8 x=F[ Top[x] ]; 9 } 10 if(dep[x]>dep[y]) swap(x,y); 11 ans=(ans+ask(1,1,n,nid[x],nid[y]))%p; 12 return ans; 13 }
1 inline void add1(int x,int y,int z) 2 { 3 z=z%p; 4 while (Top[x]!=Top[y]) 5 { 6 if(dep[ Top[x] ]<dep[ Top[y] ]) swap(x,y); 7 add(1,1,n,nid[ Top[x] ],nid[x],z); 8 x=F[ Top[x] ]; 9 } 10 if(dep[x]>dep[y]) swap(x,y); 11 add(1,1,n,nid[x],nid[y],z); 12 }
要分清楚$x$与$ID[x]$。只要$x$,$y$还不在同一条链上，就把$x$调到链头深度较深的地方；
对$ID[x]$到$ID[ Top[x] ]$($x$所在链的链头)进行区间加。把$x$跳到链头的父亲处，进入新的一条链中（两条重链之间必然由一条轻链连在一起）
当$x$，$y$到了同一条链上，就把x调到深度较浅的地方，对于$ID[x]$，$ID[y]$,这一段进行区间加。
为了不要出错，这个板子可以多打打。
完。
---shzr