bzoj2631

题解：

lct+链上修改

每一次修改的时候记录lazy标记

如果有了乘法，加法的lazy标记也要相应的随之变化

代码：

#pragma GCC optimize(2)

#include<bits/stdc++.h>

const int M=,N=;

typedef unsigned ll;

using namespace std;

int read()

{

    int x=;char ch=getchar();

    for (;ch<''||ch>'';ch=getchar());

    for (;ch>=''&&ch<='';ch=getchar())x=x*+ch-'';

    return x;

}

int n,m,top,cnt,c[N][],fa[N],size[N],q[N],rev[N];

ll sum[N],val[N],at[N],mt[N];

void cal(int x,int m,int a)

{

    if (!x)return;

    val[x]=(val[x]*m+a)%M;

    sum[x]=(sum[x]*m+a*size[x])%M;

    at[x]=(at[x]*m+a)%M;

    mt[x]=(mt[x]*m)%M;

}

int isroot(int x){return c[fa[x]][]!=x&&c[fa[x]][]!=x;}

void update(int x)

{

    int l=c[x][],r=c[x][];

    sum[x]=(sum[l]+sum[r]+val[x])%M;

    size[x]=(size[l]+size[r]+)%M;

}

void pushdown(int x)

{

    int l=c[x][],r=c[x][];

    if (rev[x])

     {

        rev[x]^=;rev[l]^=;rev[r]^=;

        swap(c[x][],c[x][]);

     }

    int m=mt[x],a=at[x];

    mt[x]=;at[x]=;

    if(m!=||a!=)cal(l,m,a),cal(r,m,a);

}

void rotate(int x)

{

    int y=fa[x],z=fa[y],l,r;

    l=(c[y][]==x);r=l^;

    if (!isroot(y))c[z][c[z][]==y]=x;

    fa[x]=z;fa[y]=x;fa[c[x][r]]=y;

    c[y][l]=c[x][r];c[x][r]=y;

    update(y);update(x);

}

void down(int x){if (!isroot(x))down(fa[x]);pushdown(x);}

void splay(int x)

{

    down(x);

    for (int y=fa[x];!isroot(x);rotate(x),y=fa[x])

     if (!isroot(y))rotate((c[y][]==x)==(c[fa[y]][]==y)?y:x);

}

void access(int x)

{

    for(int t=;x;t=x,x=fa[x])

     {

        splay(x);

        c[x][]=t;

        update(x);

     }

}

void makeroot(int x){access(x);splay(x);rev[x]^=;}

void split(int x,int y){makeroot(y);access(x);splay(x);}

void link(int x,int y){makeroot(x);fa[x]=y;}

void cut(int x,int y){makeroot(x);access(y);splay(y);c[y][]=fa[x]=;}

int main()

{

    n=read();m=read();

    for (int i=;i<=n;i++)val[i]=sum[i]=mt[i]=size[i]=;

    for (int i=;i<n;i++)

     {

        int u=read(),v=read();

        link(u,v);

     }

    char ch[];

    while(m--)

     {

        scanf("%s",ch);

        int u=read(),v=read();

        if (ch[]=='+')

         {

            int c=read();

            split(u,v);cal(u,,c);

         }

        if (ch[]=='-')

         {

            cut(u,v);

            u=read();v=read();link(u,v);

         }

        if (ch[]=='*')

         {

            int c=read();

            split(u,v);cal(u,c,);

         }

        if (ch[]=='/')

         {

            split(u,v);

            printf("%d\n",sum[u]);

         }

     }

    return ;

}