洛谷3384

1 #include
      
         2 #include
       
          3 #define ls (cur<<1)  4 #define rs (cur<<1|1)  5 #define len(x) (a[x].r-a[x].l+1)  6 #define mid ((a[cur].l+a[cur].r)>>1)   7 using namespace std;  8 const int maxn=500010;  9 int n,m,Mod,k,x,y,z,root,tot=0,num=0; 10 int v[maxn],pos[maxn],dfn[maxn],dep[maxn],son[maxn],size[maxn],fa[maxn],top[maxn],last[maxn]; 11 struct edge{
    int to,pre;}e[maxn]; 12 struct tree{
    int l,r,sum,del;}a[maxn<<2]; 13 inline void read(int &k){ 14     k=0; int f=1; char c=getchar(); 15     while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); 16     while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar(); 17     k*=f; 18 } 19 inline void MOD(int &k){
    if (k>=Mod) k-=Mod;} 20 inline void add(int x,int y){e[++tot].to=y; e[tot].pre=last[x]; last[x]=tot;} 21 void dfs1(int x){ 22     size[x]=1; dep[x]=dep[fa[x]]+1; 23     for (int i=last[x],to;i;i=e[i].pre) 24     if ((to=e[i].to)!=fa[x]){ 25         fa[to]=x; dfs1(to); 26         size[x]+=size[to]; 27         if (size[to]>size[son[x]]) son[x]=to; 28     } 29 } 30 void dfs2(int x,int tp){ 31     top[x]=tp; dfn[x]=++num; pos[num]=x; 32     if (son[x]) dfs2(son[x],tp); 33     for (int i=last[x],to;i;i=e[i].pre) 34     if ((to=e[i].to)!=fa[x]&&to!=son[x]) dfs2(to,to); 35 } 36 void build(int cur,int l,int r){ 37     a[cur].l=l; a[cur].r=r; 38     if (l
        
         mid) add(rs,l,r,delta); 58     a[cur].sum=a[ls].sum+a[rs].sum; MOD(a[cur].sum); 59 } 60 int query(int cur,int l,int r){ 61     if (l<=a[cur].l&&a[cur].r<=r) return a[cur].sum; 62     pushdown(cur); int ret=0; 63     if (l<=mid) ret+=query(ls,l,r),MOD(ret);  64     if (r>mid) ret+=query(rs,l,r),MOD(ret); 65     return ret; 66 } 67 int main(){ 68     read(n); read(m); read(root); read(Mod); 69     for (int i=1;i<=n;i++) read(v[i]),v[i]%=Mod; 70     for (int i=1;i
         
          dep[y]) swap(x,y); 81             add(1,dfn[x],dfn[y],z); 82         } 83         if (k==2){ 84             read(x); read(y); int ans=0; 85             while(top[x]!=top[y]){ 86                 if (dep[top[x]]
          
           dep[y]) swap(x,y); ans+=query(1,dfn[x],dfn[y]); MOD(ans); 90             printf("%d\n",ans); 91         }  92         if (k==3){ 93             read(x); read(y); 94             add(1,dfn[x],dfn[x]+size[x]-1,y); 95         } 96         if (k==4){ 97             read(x); 98             printf("%d\n",query(1,dfn[x],dfn[x]+size[x]-1)); 99         }100     }101     return 0;102 }