省选被暴虐，成功爆0。。。顺便ditoly差点全省总分Rank1 orz.....
于是开始赶进度学新算法。。。。
然后决定开始学习树剖orz。。。
发现树剖很好用啊！！！！
然后做了模板题。
题目就是给你一棵树，然后每次操作是查询或者增加一条树上2点路径/子树的值。
解题思路：都说了是树剖模板题，所以就要写树剖啊，然后用线段树维护。。。然后考虑多存储一下子树在线段树上的区间，就可以解决了。
期望时间效率( O( m log log^{2} n )).最坏时间复杂度: ( O( m log^{2} n )).
然后贴个版吧。。。
#include <stdio.h> #define MN (1<<17) #define mid ((l+r)>>1) #define ls (k<<1) #define rs (k<<1|1) #define v edge[i].to #define Mn 100005 struct zxy{int to,nxt;}edge[Mn<<1]; int mark[MN<<1],sum[MN<<1],n,son[Mn],head[Mn],top[Mn],siz[Mn],val[Mn],pos[Mn],fa[Mn],rpos[Mn],dep[Mn],mod,cnt,dfsn,q,root; inline int in(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar(); while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); return x*f; } inline void ins(int x,int y){edge[++cnt].to=y,edge[cnt].nxt=head[x],head[x]=cnt;} inline void dfs1(int u,int f,int d){ fa[u]=f,dep[u]=d,siz[u]=1; for (register int i=head[u]; i; i=edge[i].nxt) if (v!=f){ dfs1(v,u,d+1);siz[u]+=siz[v]; if (siz[v]>siz[son[u]]) son[u]=v; } } inline void dfs2(int u,int tp){ top[u]=tp;pos[u]=(++dfsn);if (son[u]) dfs2(son[u],tp); for (register int i=head[u]; i; i=edge[i].nxt) if (v!=fa[u]&&v!=son[u]) dfs2(v,v); rpos[u]=dfsn; } inline void pushdown(int k,int l,int r){ if (l==r||mark[k]==0) return; register int length=r-l+1; mark[ls]+=mark[k];mark[ls]%=mod; mark[rs]+=mark[k];mark[rs]%=mod; sum[ls]+=(1ll*((length-(length>>1))%mod)*mark[k])%mod;sum[ls]%=mod; sum[rs]+=(1ll*((length>>1)%mod)*mark[k])%mod;sum[rs]%=mod;mark[k]=0; } inline void combine(int k){sum[k]=sum[ls]+sum[rs];sum[k]%=mod;} inline void update(int l,int r,int a,int b,int k,int ad){ if (a<=l&&r<=b){ mark[k]+=ad;mark[k]%=mod; sum[k]+=(1ll*((r-l+1)%mod)*ad)%mod;sum[k]%=mod; return; }pushdown(k,l,r); if (a<=mid) update(l,mid,a,b,ls,ad); if (b>mid) update(mid+1,r,a,b,rs,ad); combine(k); } inline int query(int l,int r,int a,int b,int k){ if (l==a&&r==b) return sum[k];pushdown(k,l,r); if (b<=mid) return query(l,mid,a,b,ls); if (a>mid) return query(mid+1,r,a,b,rs); return (1ll*query(l,mid,a,mid,ls)+query(mid+1,r,mid+1,b,rs))%mod; } inline void Mupdate(int x,int y,int ad){ while(top[x]!=top[y]) if (dep[top[x]]>dep[top[y]]) update(1,n,pos[top[x]],pos[x],1,ad),x=fa[top[x]]; else update(1,n,pos[top[y]],pos[y],1,ad),y=fa[top[y]]; if (dep[x]<dep[y]) update(1,n,pos[x],pos[y],1,ad); else update(1,n,pos[y],pos[x],1,ad); } inline int Mquery(int x,int y){ register int res=0; while(top[x]!=top[y]) if (dep[top[x]]>dep[top[y]]) res=(1ll*res+query(1,n,pos[top[x]],pos[x],1))%mod,x=fa[top[x]]; else res=(1ll*res+query(1,n,pos[top[y]],pos[y],1))%mod,y=fa[top[y]]; if (dep[x]<dep[y]) res=(1ll*res+query(1,n,pos[x],pos[y],1))%mod; else res=(1ll*res+query(1,n,pos[y],pos[x],1))%mod;return res; } void init(){ n=in(),q=in(),root=in(),mod=in(); for (register int i=1; i<=n; ++i) val[i]=in(),val[i]%=mod; for (register int i=1; i<n; ++i){ register int x=in(),y=in(); ins(x,y);ins(y,x); }dfs1(root,root,1);dfs2(root,root); for (register int i=1; i<=n; ++i) update(1,n,pos[i],pos[i],1,val[i]); } void solve(){ while(q--){ register int op=in(); if (op&1){ if (op==1){ register int x=in(),y=in(),ad=in(); ad%=mod; Mupdate(x,y,ad); }else{ register int x=in(),ad=in(); ad%=mod; update(1,n,pos[x],rpos[x],1,ad); } } else{ if (op==2){ register int x=in(),y=in(); printf("%d ",Mquery(x,y)); }else{ register int x=in(); printf("%d ",query(1,n,pos[x],rpos[x],1)); } } } } int main(){init();solve();}