@[Mogeko](/space/show?uid=119316) l,r,ls,rs没必要存然后sum和lazy不应该开4倍吗？
by 大吉大利 @ 2019-02-17 20:44:27
@[大吉大利](/space/show?uid=50014) 不存ls和rs的话，是要下标写成now*2和now*2+1嘛..?
by Mogeko @ 2019-02-17 21:00:16
@[Mogeko](/space/show?uid=119316) 确实可以，记录下来一般都是动态开点（你写的那种）吧，但是不知道为啥你会MLE
by 大吉大利 @ 2019-02-17 21:15:29
@[Mogeko](/space/show?uid=119316) 您貌似是写挂了qwq，写法不同看不大懂
by 小何の儿子 @ 2019-02-17 22:33:46
@[大吉大利](/space/show?uid=50014) 谢谢，不记录l，r，ls，rs之后过了qwq
by Mogeko @ 2019-02-18 08:43:55
@[小何の儿子](/space/show?uid=61872) 解决了，谢谢qwq
by Mogeko @ 2019-02-18 08:44:23
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#define MogeKo qwq
using namespace std;
const int maxn = 1e5+10;
int n,m,rt,opt,x,y,z,mod,cnt;
int to[maxn<<1],head[maxn<<1],nxt[maxn<<1];
long long sum[maxn<<2],lazy[maxn<<2];
int dfn[maxn],dpth[maxn],siz[maxn],hson[maxn],fa[maxn],top[maxn],point[maxn];
long long w[maxn];
void add(int x,int y){
to[++cnt] = y;
nxt[cnt] = head[x];
head[x] = cnt;
}
void dfs1(int u){
dpth[u] = dpth[fa[u]]+1;
siz[u] = 1;
for(int i = head[u];i;i = nxt[i]){
int v = to[i];
if(v == fa[u])continue;
fa[v] = u;
dfs1(v);
siz[u] += siz[v];
if(siz[v] > siz[hson[u]]) hson[u] = v;
}
}
void dfs2(int u,int t){
dfn[u] = ++cnt;
point[cnt] = u;
top[u] = t;
if(!hson[u])return;
dfs2(hson[u],t);
for(int i = head[u];i;i = nxt[i]){
int v = to[i];
if(v == fa[u] || v == hson[u])continue;
dfs2(v,v);
}
}
void build(int L,int R,int l,int r,int now){
if(l == r){
sum[now] = w[point[l]] %mod;
return;
}
int mid = l+r>>1;
if(R <= mid) build(L,R,l,mid,now<<1);
else if(L > mid) build(L,R,mid+1,r,now<<1|1);
else build(L,R,l,mid,now<<1),build(L,R,mid+1,r,now<<1|1);
sum[now] = (sum[now<<1] + sum[now<<1|1]) %mod;
}
void pushdown(int l,int r,int now){
sum[now] += (r-l+1)*lazy[now]%mod;
(lazy[now<<1] += lazy[now]) %=mod;
(lazy[now<<1|1] += lazy[now]) %=mod;
lazy[now] = 0;
}
void modify(int L,int R,int l,int r,int c,int now){
if(L <= l && r <= R){
lazy[now] += c;
return;
}
(sum[now] += (R-L+1)*c ) %=mod;
int mid = l+r>>1;
if(R <= mid) modify(L,R,l,mid,c,now<<1);
else if(L >= mid+1) modify(L,R,mid+1,r,c,now<<1|1);
else modify(L,mid,l,mid,c,now<<1),modify(mid+1,R,mid+1,r,c,now<<1|1);
}
long long query(int L,int R,int l,int r,int now){
if(L <= l && r <= R){
return (sum[now]+lazy[now]*(r-l+1))%mod;
}
pushdown(l,r,now);
int mid = l+r>>1;
if(R <= mid) return query(L,R,l,mid,now<<1);
else if(L >= mid+1) return query(L,R,mid+1,r,now<<1|1);
else return (query(L,mid,l,mid,now<<1) + query(mid+1,R,mid+1,r,now<<1|1)) %mod;
}
void getmodify(int x,int y,int c){
while(top[x] != top[y]){
if(dpth[top[x]] < dpth[top[y]]) swap(x,y);
modify(dfn[top[x]],dfn[x],1,n,c,1);
x = fa[top[x]];
}
if(dpth[x] > dpth[y]) swap(x,y);
modify(dfn[x],dfn[y],1,n,c,1);
}
long long getquery(int x,int y){
long long ans = 0;
while(top[x] != top[y]){
if(dpth[top[x]] < dpth[top[y]]) swap(x,y);
(ans += query(dfn[top[x]],dfn[x],1,n,1)) %=mod;
x = fa[top[x]];
}
if(dpth[x] > dpth[y]) swap(x,y);
(ans += query(dfn[x],dfn[y],1,n,1)) %=mod;
return ans;
}
int main(){
scanf("%d%d%d%d",&n,&m,&rt,&mod);
for(int i = 1;i <= n;i++)
scanf("%lld",&w[i]);
for(int i = 1;i <= n-1;i++){
scanf("%d%d",&x,&y);
add(x,y),add(y,x);
}
cnt = 0,dfs1(rt),dfs2(rt,rt);
cnt = 0,build(1,n,1,n,++cnt);
for(int i = 1;i <= m;i++){
scanf("%d",&opt);
if(opt == 1){
scanf("%d%d%d",&x,&y,&z);
getmodify(x,y,z%mod);
}
if(opt == 2){
scanf("%d%d",&x,&y);
printf("%lld\n",getquery(x,y));
}
if(opt == 3){
scanf("%d%d",&x,&z);
modify(dfn[x],dfn[x]+siz[x]-1,1,n,z%mod,1);
}
if(opt == 4){
scanf("%d",&x);
printf("%lld\n",query(dfn[x],dfn[x]+siz[x]-1,1,n,1));
}
}
return 0;
}
```
by Mogeko @ 2019-02-18 08:44:41