省选被暴虐，成功爆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<<];
int mark[MN<<],sum[MN<<],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=,f=; char ch=getchar();
while(ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while(ch>=''&&ch<='') x=(x<<)+(x<<)+ch-'',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]=;
for (register int i=head[u]; i; i=edge[i].nxt)
if (v!=f){
dfs1(v,u,d+);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]==) return;
register int length=r-l+;
mark[ls]+=mark[k];mark[ls]%=mod;
mark[rs]+=mark[k];mark[rs]%=mod;
sum[ls]+=(1ll*((length-(length>>))%mod)*mark[k])%mod;sum[ls]%=mod;
sum[rs]+=(1ll*((length>>)%mod)*mark[k])%mod;sum[rs]%=mod;mark[k]=;
}
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+)%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+,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+,r,a,b,rs);
return (1ll*query(l,mid,a,mid,ls)+query(mid+,r,mid+,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(,n,pos[top[x]],pos[x],,ad),x=fa[top[x]];
else update(,n,pos[top[y]],pos[y],,ad),y=fa[top[y]];
if (dep[x]<dep[y]) update(,n,pos[x],pos[y],,ad);
else update(,n,pos[y],pos[x],,ad);
}
inline int Mquery(int x,int y){
register int res=;
while(top[x]!=top[y])
if (dep[top[x]]>dep[top[y]])
res=(1ll*res+query(,n,pos[top[x]],pos[x],))%mod,x=fa[top[x]];
else res=(1ll*res+query(,n,pos[top[y]],pos[y],))%mod,y=fa[top[y]];
if (dep[x]<dep[y]) res=(1ll*res+query(,n,pos[x],pos[y],))%mod;
else res=(1ll*res+query(,n,pos[y],pos[x],))%mod;return res;
}
void init(){
n=in(),q=in(),root=in(),mod=in();
for (register int i=; i<=n; ++i) val[i]=in(),val[i]%=mod;
for (register int i=; i<n; ++i){
register int x=in(),y=in();
ins(x,y);ins(y,x);
}dfs1(root,root,);dfs2(root,root);
for (register int i=; i<=n; ++i) update(,n,pos[i],pos[i],,val[i]);
}
void solve(){
while(q--){
register int op=in();
if (op&){
if (op==){
register int x=in(),y=in(),ad=in(); ad%=mod;
Mupdate(x,y,ad);
}else{
register int x=in(),ad=in(); ad%=mod;
update(,n,pos[x],rpos[x],,ad);
}
}
else{
if (op==){
register int x=in(),y=in();
printf("%d\n",Mquery(x,y));
}else{
register int x=in();
printf("%d\n",query(,n,pos[x],rpos[x],));
}
}
}
}
int main(){init();solve();}