最近好像掉进什么奇怪的数据结构坑里去了。。。。

先放个板子，讲解和例题到时候在补上

# include
     
      # include
      
       # include
       
        # include
        
         # include
         
          # include
          
           using std::swap;const int mn = 200005;struct edge{ int to,next;};edge e[mn*2];int head[mn],edge_max;int n,m,r,mod;int val[mn],w[mn];int deep[mn],siz[mn],fa[mn];int id[mn],bl[mn],tot;struct tree{ int l,r,sum,lazy;};tree tr[mn*4];void add(int x,int y){ e[++edge_max].to=y; e[edge_max].next=head[x]; head[x]=edge_max;}void dfs1(int x){ siz[x]=1; for(int i=head[x];i;i=e[i].next) { int u=e[i].to; if(u!=fa[x]) { deep[u]=deep[x]+1; fa[u]=x; dfs1(u); siz[x]+=siz[u]; } }}void dfs2(int x,int chain){ int k=0; id[x]=++tot; w[tot]=val[x]; bl[x]=chain; for(int i=head[x];i;i=e[i].next) { int u=e[i].to; if(deep[u]>deep[x] && siz[u]>siz[k]) k=u; } if(!k) return ; dfs2(k,chain); for(int i=head[x];i;i=e[i].next) { int u=e[i].to; if(deep[u]>deep[x] && u!=k) dfs2(u,u); }}void build(int l,int r,int cur){ tr[cur].l=l,tr[cur].r=r; if(l==r) { tr[cur].sum=(w[l])%mod; return ; } int mid=l+r>>1; build(l,mid,cur<<1); build(mid+1,r,cur<<1|1); tr[cur].sum=(tr[cur<<1].sum+tr[cur<<1|1].sum)%mod;}void pushdown(int cur){ if(tr[cur].lazy!=0) { tr[cur<<1].sum=(tr[cur<<1].sum+(tr[cur<<1].r-tr[cur<<1].l+1)*tr[cur].lazy)%mod; tr[cur<<1|1].sum=(tr[cur<<1|1].sum+(tr[cur<<1|1].r-tr[cur<<1|1].l+1)*tr[cur].lazy)%mod; tr[cur<<1].lazy=(tr[cur<<1].lazy+tr[cur].lazy)%mod; tr[cur<<1|1].lazy=(tr[cur<<1|1].lazy+tr[cur].lazy)%mod; tr[cur].lazy=0; } return ;}void update(int cur,int L,int R,int x){ if(tr[cur].l>R || tr[cur].r
           
            =L && tr[cur].r<=R) { tr[cur].sum=((tr[cur].r-tr[cur].l+1)*x+tr[cur].sum)%mod; tr[cur].lazy=(tr[cur].lazy+x)%mod; return ; } pushdown(cur); update(cur<<1,L,R,x); update(cur<<1|1,L,R,x); tr[cur].sum=(tr[cur<<1].sum+tr[cur<<1|1].sum)%mod;}void treeadd(int x,int y,int z){ while(bl[x]!=bl[y]) { if(deep[bl[x]]
            
             deep[y]) swap(x,y); update(1,id[x],id[y],z);}int query(int cur,int L,int R){ if(tr[cur].l>=L && tr[cur].r<=R) return tr[cur].sum; if(tr[cur].l>R || tr[cur].r
             
              deep[y]) swap(x,y); ret=(ret+query(1,id[x],id[y]))%mod; printf("%d\n",ret);}int main(){ int x,y,opt,z; scanf("%d%d%d%d",&n,&m,&r,&mod); for(int i=1;i<=n;i++) scanf("%d",&val[i]); for(int i=1;i