【LCT】Tree

一眼动态树问题。 注意：

1. 维护了两个懒标记，其中加法的懒标记默认为0，乘法懒标记为1。
2. 先算乘法，再算加法，a->b 之间的路径都改变，意思是我只把 a->b 的路径拿下来，然后给根节点打上标记 。

Code

#include<bits/stdc++.h>
#define lc c[x][0]
#define rc c[x][1]
#define add(x,c) x+=c,x%=mod
#define mul(x,c) x*=c,x%=mod
using namespace std;
const int N=1e5+12,mod=51061;
long long v[N],c[N][2],lazy1[N],lazy2[N],st[N],a[N];
int siz[N],r[N],head[N],cnt,n,q,u1,v1,u2,v2,f[N],k;
char op;
//lazy1为+，lazy2为*
void pushup(int x)
{
  v[x]=(v[lc]+v[rc]+a[x])%mod;
  siz[x]=siz[lc]+siz[rc]+1;
}
void pushr(int x)
{
  int t=lc;
  lc=rc,rc=t,r[x]^=1;
}
void pusha(int x,int c)
{
  add(v[x],siz[x]*c),add(a[x],c),add(lazy1[x],c);
}
void pushm(int x,int c)
{
  mul(v[x],c),mul(a[x],c),mul(lazy2[x],c),mul(lazy1[x],c);
}
void pushdown(int x)
{
    if( lazy2[x]!=1 )
  {
    if( lc ) pushm(lc,lazy2[x]);
    if( rc ) pushm(rc,lazy2[x]);
    lazy2[x]=1;
  }
    if( lazy1[x] )
  {
    if( lc ) pusha(lc,lazy1[x]);
    if( rc ) pusha(rc,lazy1[x]);
    lazy1[x]=0;
  }
  if( r[x] )
  {
    if( lc ) pushr(lc);  //左儿子更新
    if( rc ) pushr(rc);  //右儿子更新
    r[x]=0;     //标记归零
  }

}
bool nroot(int x)
{
  return c[f[x]][0]==x || c[f[x]][1]==x;
}
void rotate(int x)
{
  int y=f[x],z=f[y],k=c[y][1]==x,w=c[x][!k];
  if( nroot(y) ) c[ z ][ c[z][1]==y ]=x;
  c[x][!k]=y;c[y][k]=w;
  if( w ) f[w]=y;
  f[y]=x;f[x]=z;
  pushup(y);
  pushup(x);
}
void splay(int x)
{
  int y=x,z=0;
  st[++z]=y;
  while( nroot(y) ) st[++z]=y=f[y];
  while(   z      ) pushdown(st[z--]);
  while( nroot(x) )
  {
    y=f[x],z=f[y];
    if( nroot(y) ) rotate( (c[y][0]==x)^(c[z][0]==y)?x:y );
    rotate(x);
  }
  pushup(x);
}
void access(int x)
{
  for(int y=0;x;x=f[y=x])
  {
    splay(x),rc=y,pushup(x);}
}
void makeroot(int x)
{
  access(x);
  splay(x);
  pushr(x);
}
void split(int x,int y)
{
  makeroot(x);
  access(y);splay(y);
}
void link(int x,int y)
{
  makeroot(x);
  f[x]=y;
}
void cut(int x,int y)
{
  split(x,y);
  f[x]=c[y][0]=0;
}
int main(){
  cin>>n>>q;
  for(int i=1;i<=n;i++) siz[i]=a[i]=lazy2[i]=1;
  for(int i=1;i<n;i++)
  {
    cin>>u1>>v1;
    link(u1,v1);
  }
  while(q--)
  {
   cin>>op;
   if( op=='+' )
   {
     cin>>u1>>v1>>k;
     split(u1,v1);
     pusha(v1,k);
   }
  if( op=='-' )
  {
    cin>>u1>>v1>>u2>>v2;
    cut(u1,v1);
    link(u2,v2);
  }
  if( op=='*' )
  {
    cin>>u1>>v1>>k;
    split(u1,v1);
    pushm(v1,k);
  }
  if(op=='/')
  {
    cin>>u1>>v1;
      split(u1,v1);
    cout<<v[v1]<<endl;
  }
  }

}