```cpp
if(size[to]>maxson){
maxson=size[u];
son[u]=to;
}
```
那里的maxson不该赋值为size[to]吗
by mzgwty @ 2019-08-03 09:11:17
您还应该再弄一个数组，存每个节点在线段树中的位置
by mzgwty @ 2019-08-03 09:16:00
@[Old_Wang](/space/show?uid=79075) 改完了开始wa
```cpp
#include<cstdio>
#include<iostream>
#define rint register int
using namespace std;
const int N=500005;
int u[N],v[N],first[N],next[N];
int dpt[N],fa[N],son[N],top[N],idx[N],size[N],val[N],pre[N];
int tot,cnt;
int n,m,r,mod;
int read(){
int f=1,x=0;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return f*x;
}
void add(int x,int y){
u[++tot]=x,v[tot]=y;
next[tot]=first[x];
first[x]=tot;
}
void dfs1(int u,int pa,int depth){
fa[u]=pa;
dpt[u]=depth;
size[u]=1;
int maxson=-1;
for(rint i=first[u];i;i=next[i]){
int to=v[i];
if(to==pa) continue;
dfs1(to,u,depth+1);
size[u]+=size[to];
if(size[to]>maxson){
maxson=size[to];
son[u]=to;
}
}
}
void dfs2(int u,int tp){
idx[u]=++cnt;
top[u]=tp;
val[cnt]=pre[u];
if(son[u]) dfs2(son[u],tp);
for(rint i=first[u];i;i=next[i]){
if(!idx[v[i]]&&v[i]!=fa[u]){
dfs2(v[i],v[i]);
}
}
}
struct SegmentTree{
int l,r,sum,lazy;
#define ls p<<1
#define rs p<<1|1
}t[4*N];
void pushup(int p){
t[p].sum=(t[ls].sum+t[rs].sum)%mod;;
}
void pushdown(int p){
if(t[p].lazy){
t[ls].lazy=(t[ls].lazy+t[p].lazy)%mod;
t[rs].lazy=(t[rs].lazy+t[p].lazy)%mod;
t[p].lazy=0;
t[ls].sum=(t[ls].sum+t[p].lazy*(t[ls].r-t[ls].l+1))%mod;
t[rs].sum=(t[rs].sum+t[p].lazy*(t[rs].r-t[ls].l+1))%mod;
}
}
void build(int p,int l,int r){
t[p].l=l,t[p].r=r;
if(l==r){t[p].sum=pre[l];return;}
int mid=(l+r)/2;
build(ls,l,mid);
build(rs,mid+1,r);
pushup(p);
}
void add(int p,int l,int r,int k){
if(t[p].l>=l&&t[p].r<=r){
t[p].sum=(t[p].sum+k*(t[p].r-t[p].l+1))%mod;
t[p].lazy=(t[p].lazy+k)%mod;
return;
}
int mid=(t[p].l+t[p].r)/2;
pushdown(p);
if(l<=mid) add(ls,l,r,k);
if(r>mid) add(rs,l,r,k);
pushup(p);
}
int ask(int p,int l,int r){
pushdown(p);
if(t[p].l>=l&&t[p].r<=r){
return t[p].sum%mod;
}
int val=0;
int mid=(t[p].l+t[p].r)/2;
if(l<=mid) val=(val+ask(ls,l,r))%mod;
if(r>mid) val=(val+ask(rs,l,r))%mod;
return val%mod;
}
void addpath(int x,int y,int k){
while(top[x]!=top[y]){
if(dpt[top[x]]<dpt[top[y]]) swap(x,y);
add(1,idx[top[x]],idx[x],k);
x=fa[top[x]];
}
if(dpt[x]>dpt[y]) swap(x,y);
add(1,idx[x],idx[y],k);
}
int askpath(int x,int y){
int sum=0;
while(top[x]!=top[y]){
if(dpt[top[x]]<dpt[top[y]]) swap(x,y);
sum=(sum+ask(1,idx[top[x]],idx[x]))%mod;
x=fa[top[x]];
}
if(dpt[x]>dpt[y]) swap(x,y);
sum=(sum+ask(1,idx[x],idx[y]))%mod;
return sum;
}
void addtree(int x,int k){
add(1,idx[x],idx[x]+size[x]-1,k);
return;
}
int asktree(int x){
int sum=0;
sum=ask(1,idx[x],idx[x]+size[x]-1)%mod;
return sum;
}
int main(){
n=read(),m=read(),r=read(),mod=read();
for(rint i=1;i<=n;i++) pre[i]=read();
for(rint i=1;i<n;i++){
int a=read(),b=read();
add(a,b),add(b,a);
}
dfs1(r,0,1);
dfs2(r,r);
build(1,1,n);
while(m--){
int opt=read();
switch(opt){
case 1:{
int x=read(),y=read(),z=read();
z=z%mod;
addpath(x,y,z);
break;
}
case 2:{
int x=read(),y=read();
int ans=askpath(x,y);
printf("%d\n",ans);
break;
}
case 3:{
int x=read(),z=read();
z=z%mod;
addtree(x,z);
break;
}
case 4:{
int x=read();
int ans=asktree(x);
printf("%d\n",ans);
break;
}
}
}
return 0;
}
```
by RoRoyyy @ 2019-08-03 09:18:01
不是$add(1,top[x],x,k)$
设节点在线段树中的位置为seg[x],
则应该是$add(1,seg[top[x]],seg[x],k)$
其他同理
by mzgwty @ 2019-08-03 09:19:46
emming
by mzgwty @ 2019-08-03 09:21:16
@[Old_Wang](/space/show?uid=79075) 改过了还wa
by RoRoyyy @ 2019-08-03 09:21:52
显然手机打字太慢了
by mzgwty @ 2019-08-03 09:21:54
@[Old_Wang](/space/show?uid=79075) 还有啥问题么....
by RoRoyyy @ 2019-08-03 09:25:01
lazy标记没放错位置吗
by Mr_Skirt @ 2019-08-03 09:26:33
@[Mr_Skirt](/space/show?uid=36956) 哪处
by RoRoyyy @ 2019-08-03 09:27:18