题解
树链剖分模板题，以后再写详细的树链剖分（让我多做几道题）
先放代码，以后再补充详细的解释（留个坑）#include#include #include #include #include #include using namespace std;#define MAX 120000#define MAXL MAX+MAX#define lson (now<<1)#define rson ((now<<1)|1)inline int read(){ register int x=0,t=1; register char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-')ch=getchar(); if(ch=='-'){t=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();} return x*t;}struct Line{ int v,next,w;}e[MAXL];int h[MAX],cnt=1;int dep[MAX],hson[MAX],size[MAX],f[MAX],VV[MAX],V[MAX];int top[MAX],idb[MAX],ide[MAX],tot,N,M,P,R,line[MAX];struct Node{ int val,lazy;}c1[MAX*8];inline void Add(int u,int v){ e[cnt]=(Line){v,h[u]}; h[u]=cnt++; }void DFS1(int u,int ff){ dep[u]=dep[ff]+1;//求深度 size[u]=1;//子树大小 hson[u]=0;//重儿子 f[u]=ff;//父亲 int v; for(int i=h[u];i;i=e[i].next) { v=e[i].v; if(v==ff)continue; DFS1(v,u); size[u]+=size[v]; if(size[v]>size[hson[u]])hson[u]=v;//求出重儿子 }}void DFS2(int u,int ff){ top[u]=ff;//重链顶端 idb[u]=++tot;//DFS序 line[tot]=u; if(hson[u])DFS2(hson[u],ff);//强制先走重链 for(int i=h[u];i;i=e[i].next) { int v=e[i].v; if(v==f[u]||v==hson[u])continue; DFS2(v,v);//走轻链 } ide[u]=tot;//子树结束位置 }void pushdown1(int now,int l,int r){ c1[now].val=(c1[now].val+1LL*(r-l+1)*c1[now].lazy)%P; c1[lson].lazy=(c1[lson].lazy+c1[now].lazy)%P; c1[rson].lazy=(c1[rson].lazy+c1[now].lazy)%P; c1[now].lazy=0;}void build1(int now,int l,int r){ if(l==r){c1[now].val=V[line[l]];return;} int mid=(l+r)>>1; build1(lson,l,mid);build1(rson,mid+1,r); c1[now].val=(c1[lson].val+c1[rson].val)%P;}void update1(int now,int l,int r,int al,int ar,int w){ if(al==l&&ar==r){c1[now].lazy+=w;return;} int mid=(l+r)>>1; (c1[now].val+=1LL*(ar-al+1)*w)%=P; if(ar<=mid)update1(lson,l,mid,al,ar,w); else if(al>mid)update1(rson,mid+1,r,al,ar,w); else {update1(lson,l,mid,al,mid,w);update1(rson,mid+1,r,mid+1,ar,w);}}int Query1(int now,int l,int r,int al,int ar){ pushdown1(now,l,r); if(al==l&&ar==r)return c1[now].val%P; int mid=(l+r)>>1; if(ar<=mid)return Query1(lson,l,mid,al,ar); if(al>mid)return Query1(rson,mid+1,r,al,ar); return (Query1(lson,l,mid,al,mid)+Query1(rson,mid+1,r,mid+1,ar))%P;}void Change(int u,int v,int w){ int tp1=top[u],tp2=top[v]; while(tp1!=tp2) { if(dep[tp1]