树链剖分->链加、链和、子树加、子树和
树状数组->区间加、区间和
链上操作是树剖最基本的操作了，剖完可以用树状数组或是线段树维护一下，子树操作只要搞出做树剖时的dfs序就可以了，剖出的链和子树都是连续的区间。
因为9018上好像没有树剖的模板，学长就说要加，随便打了打交洛谷上居然挂了，查了好久发现写了if(i==1)i=read(),Tadd(x,i,read());if(i==2)……这种代码，1号操作中如果输入了2、3、4之类的程序就会挂……虽然之前遇到过这种问题了，但这次居然恰好过了样例QAQ。重用变量需谨慎。
#include<cstdio> char B[1<<26],*S=B,C;int X; inline int read() { while((C=*S++)<'0'||C>'9'); for(X=C-'0';(C=*S++)>='0'&&C<='9';)X=(X<<3)+(X<<1)+C-'0'; return X; } #define MN 100000 struct edge{int nx,t;}e[MN*2+5]; int p,a[MN+5],h[MN+5],en,fa[MN+5],s[MN+5],mx[MN+5],d[MN+5]; int f[MN+5],l[MN+5],r[MN+5],dfn,s1[MN+5],s2[MN+5]; void inc(int*s,int x,int z){for(;x<=MN;x+=x&-x)s[x]=(s[x]+z)%p;} int sum(int*s,int x){int r=0;for(;x;x-=x&-x)r=(r+s[x])%p;return r;} void add(int l,int r,int x) { inc(s1,l,x);inc(s1,r+1,-x); inc(s2,l,1ll*x*(l-1)%p);inc(s2,r+1,-1ll*x*r%p); } int query(int l,int r) { return((1ll*r*sum(s1,r)-(l-1ll)*sum(s1,l-1)-sum(s2,r)+sum(s2,l-1))%p+p)%p; } inline void ins(int x,int y) { e[++en]=(edge){h[x],y};h[x]=en; e[++en]=(edge){h[y],x};h[y]=en; } void pre(int x) { s[x]=1; for(int i=h[x];i;i=e[i].nx)if(e[i].t!=fa[x]) { fa[e[i].t]=x;d[e[i].t]=d[x]+1;pre(e[i].t); s[x]+=s[e[i].t];if(s[e[i].t]>s[mx[x]])mx[x]=e[i].t; } } void dfs(int x,int k) { f[x]=k;l[x]=++dfn;add(dfn,dfn,a[x]); if(mx[x])dfs(mx[x],k); for(int i=h[x];i;i=e[i].nx) if(e[i].t!=fa[x]&&e[i].t!=mx[x])dfs(e[i].t,e[i].t); r[x]=dfn; } void Tadd(int x,int y,int z) { while(f[x]!=f[y]) if(d[f[x]]>d[f[y]])add(l[f[x]],l[x],z),x=fa[f[x]]; else add(l[f[y]],l[y],z),y=fa[f[y]]; d[x]<d[y]?add(l[x],l[y],z):add(l[y],l[x],z); } int Tquery(int x,int y) { int r=0; while(f[x]!=f[y]) if(d[f[x]]>d[f[y]])r=(r+query(l[f[x]],l[x]))%p,x=fa[f[x]]; else r=(r+query(l[f[y]],l[y]))%p,y=fa[f[y]]; return (r+(d[x]<d[y]?query(l[x],l[y]):query(l[y],l[x])))%p; } int main() { fread(B,1,1<<26,stdin); int n,m,rt,i,x,y; n=read();m=read();rt=read();p=read(); for(i=1;i<=n;++i)a[i]=read(); for(i=1;i<n;++i)ins(read(),read()); pre(rt);dfs(rt,rt); while(m--) { i=read();x=read(); if(i==1)y=read(),Tadd(x,y,read()); if(i==2)printf("%d ",Tquery(x,read())); if(i==3)add(l[x],r[x],read()); if(i==4)printf("%d ",query(l[x],r[x])); } }