题目链接：http://www.lydsy.com:808/JudgeOnline/problem.php?id=3589

题意：给出一棵有根树，两种操作：（1）以u为根的子树所有节点权值加上一个数字；（2）给出若干个链，求这些链的节点的权值和。重复的节点的权值只计算一次。

思路：AAA树：每个节点有四个孩子，0和1是动态树的左右孩子，其他的孩子弄成一个二叉树保存在2 3号节点上。

 

void add(i64 &x,i64 y){	x=(x+y)&(mod-1);}struct node{    node *c[4],*p;    i64 chainMark,treeMark;	int size;	i64 sum;      int inner,rev;	i64 val;      node()    {        c[0]=c[1]=c[2]=c[3]=p=0;        inner=1;        rev=0;        val=0;		sum=0;		size=1;    }      node(int x)    {        c[0]=c[1]=c[2]=c[3]=p=0;        inner=0;        rev=0;        val=x;		size=1;        pushUp();    }      void pushUp()    {        if(!inner) sum=val,size=1;		else size=1;        int i;        for(i=0;i<2;i++) if(c[i])        {			size+=c[i]->size;			add(sum,c[i]->sum);        }    }      void reverse()    {		swap(c[0],c[1]);        rev^=1;    }      void updateChain(i64 a)    {		add(chainMark,a);		add(sum,size*a);		add(val,a);    }      void updateTree(i64 a,int flag=1)    {		add(treeMark,a);        if(flag) updateChain(a);    }      void pushDown()    {        if(rev)        {            if(c[0]) c[0]->reverse();            if(c[1]) c[1]->reverse();            rev=0;        }        if(treeMark)        {            int i;            for(i=0;i<4;i++) if(c[i]) c[i]->updateTree(treeMark,i>=2);            treeMark=0;        }        if(chainMark)        {            if(c[0]) c[0]->updateChain(chainMark);            if(c[1]) c[1]->updateChain(chainMark);            chainMark=0;        }    }      int isRoot(int t)    {        if(t==0) return !p||(p->c[0]!=this&&p->c[1]!=this);        return !p||!p->inner||!inner;    }      void setSon(node *son,int id)    {        c[id]=son;        if(son) son->p=this;    }      int pos()    {        int i;        for(i=0;i<4;i++) if(p->c[i]==this) return i;        return -1;    }      node* getSon(int id)    {        if(c[id]) c[id]->pushDown();        return c[id];    }      int dir(int t)    {        return p->c[t+1]==this;    }};    /** *t=0 d=0: 右旋 *t=0 d=1: 左旋 * * **/void rot(node *u,int t){    node *p=u->p;    int d=u->dir(t);    if(p->p) p->p->setSon(u,p->pos());    else u->p=0;    p->setSon(u->c[!d+t],d+t);    u->setSon(p,!d+t);    p->pushUp();}  /** *t=0 or 2 * **/void splay(node *u,int t=0){    while(!u->isRoot(t))    {        if(u->p->isRoot(t)) rot(u,t);        else if(u->p->dir(t)==u->dir(t)) rot(u->p,t),rot(u,t);        else rot(u,t),rot(u,t);    }    u->pushUp();}    /** *把节点u的父亲设为v * **/void add(node *u,node *v){    v->pushDown();    int i;    for(i=2;i<4;i++) if(!v->c[i])    {        v->setSon(u,i);        return;    }      node *tmp=v,*x=new node;    while(tmp->c[2]->inner) tmp=tmp->getSon(2);    x->setSon(tmp->c[2],2);    x->setSon(u,3);    tmp->setSon(x,2);    splay(x,2);}    /** *将节点u从其父节点断开 * **/void del(node *u){    if(u->p->inner)    {		node *q=u->p->c[5-u->pos()];        u->p->p->setSon(q,u->p->pos());        node *tmp=u->p;		splay(u->p->p,2);        delete tmp;    }    else    {        u->p->setSon(0,u->pos());    }    u->p=0;}    node *st[N];int top;      void pushDown(node *u){    top=0;    while(u) st[++top]=u,u=u->p;    while(top>0) st[top]->pushDown(),top--;  }    void access(node *u){    node *v=u,*tmp;    pushDown(u);    splay(u);    if(u->c[1]) tmp=u->c[1],u->c[1]=0,add(tmp,u),u->pushUp();      while(u->p)    {        for(tmp=u->p;tmp->inner;tmp=tmp->p);        splay(tmp);        if(tmp->c[1])        {            u->p->setSon(tmp->c[1],u->pos());            splay(u->p,2);            tmp->setSon(u,1);        }        else        {            del(u);            tmp->setSon(u,1);        }          u=tmp;        u->pushUp();    }    splay(v);}    void makeRoot(node *u){    access(u);    u->reverse();}   int n,m;node *a[N];   vector
     
       g[N];int f[N][20];int dep[N]; void DFS(int u,int pre,int d){    f[u][0]=pre;    dep[u]=d;             int i;    for(i=0;i
      
       pushUp();} void init(){    DFS(1,0,1);    int i,j;    for(i=1;i<20;i++) for(j=1;j<=n;j++)    {        f[j][i]=f[f[j][i-1]][i-1];    }}  int jump(int u,int x){    int i;    for(i=0;i<20;i++) if(x&(1<
       
        =0;i--) if(f[u][i]&&f[v][i]&&f[u][i]!=f[v][i])    {        u=f[u][i];        v=f[v][i];    }    return f[u][0];}  struct Query{    int u,v;     void get()    {        u=getInt();        v=getInt();        if(dep[u]
        
         sum;     return ans;}  int main(){      n=getInt();    int i;    for(i=0;i
         
          val+=det;            for(i=2;i<4;i++) if(p->c[i]) p->c[i]->updateTree(det);            p->pushUp();        }        else        {            int K=getInt();            Query q[10];            for(i=1;i<=K;i++) q[i].get();            sort(q+1,q+K+1);             i64 ans=0;            for(i=1;i<=K;i++)            {                int j;                for(j=1;j
          
           dep[q[i].v]) q[i].v=lca; } ans+=cal(q[i].u,q[i].v); } ans%=mod; if(ans<0) ans+=mod; output(ans); puts(""); makeRoot(a[1]); } }}