bzoj 2759一个动态树好题

真的是动态树好题，如果把每个点的父亲设成p[x]，那么建出来图应该是一个环套树森林，拆掉一条边，就变成了动态树，考虑维护什么，对于LCT上每个节点，维护两组k和b，一组是他到他父亲的，一组是他LCT子树中深度最深的点到深度最浅的点的父亲的k和b，查询时只需查询一颗树中sf到自己的k和b，判断是否有唯一解，然后再解就可以了。注意不能换根，因为树的形态是固定的。

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 #define N 30005

 #define mod 10007

 using namespace std;

 int n,p[N],q;

 int qp(int a,int b){

     int c=;

     while(b){

         if(b&)c=c*a%mod;

         a=a*a%mod;b>>=;

     }

     return c;

 }

 struct Node{

     Node *ch[],*fa,*sf;

     int k,b,sumk,sumb,id;

     Node();

     void pushup();

     void pushdown();

 }*null=new Node,tree[N];

 Node :: Node (){

     ch[]=ch[]=fa=sf=null;

     k=sumk=;b=sumb=id=;

 }

 void Node :: pushup(){

     sumk=k;sumb=b;

     sumb=(sumk*ch[]->sumb%mod+sumb)%mod;sumk=ch[]->sumk*sumk%mod;

     sumb=(ch[]->sumk*sumb%mod+ch[]->sumb)%mod;sumk=sumk*ch[]->sumk%mod;

 }

 void rotate(Node *x){

     Node *y=x->fa,*z=y->fa;

     int w=y->ch[]==x;

     x->ch[w]->fa=y;y->ch[w^]=x->ch[w];

     y->fa=x;x->ch[w]=y;

     if(z->ch[]==y)z->ch[]=x;

     if(z->ch[]==y)z->ch[]=x;

     x->fa=z;

     y->pushup();x->pushup();

 }

 bool isroot(Node *x){

     return x->fa->ch[]!=x && x->fa->ch[]!=x;

 }

 void splay(Node *x){

     Node *y,*z;

     while(!isroot(x)){

         y=x->fa;z=y->fa;

         if((z->ch[]==y&&y->ch[]==x)||(z->ch[]==y&&y->ch[]==x))

             rotate(y);

         rotate(x);

     }

 }

 void access(Node *x){

     Node *y=null;

     while(x!=null){

         splay(x);

         x->ch[]=y;

         x->pushup();

         y=x;x=x->fa;

     }

 }

 Node * find(Node *x){

     access(x);splay(x);

     while(x->ch[]!=null)x=x->ch[];

     return x;

 }

 void cut(Node *x){

     Node *rt=find(x);

     if(rt==x)x->sf=null;

     else{

         access(x);

         splay(x);

         x->ch[]->fa=null;

         x->ch[]=null;

         x->pushup();

         if(find(rt->sf)!=find(rt)){

             rt->fa=rt->sf;

             rt->sf=null;

         }

     }

 }

 void link(Node *x,Node *f,int k,int b){

     x->k=k;x->b=b;

     if(find(f)==find(x))x->sf=f;

     else x->fa=f;

 }

 int query(Node *x){

     Node *rt=find(x),*now=rt->sf;

     access(now);splay(now);

     if(now->sumk==){

         if(now->sumb==)return -;

         else return -;

     }

     int ans=(mod-now->sumb)*qp(((now->sumk-)+mod)%mod,mod-)%mod;

     access(x);splay(x);

     return (ans*x->sumk%mod+x->sumb)%mod;

 }

 int main(){

     srand();

     null->fa=null->ch[]=null->ch[]=null->sf=null;

     scanf("%d",&n);

     for(int i=,k,b;i<=n;i++){

         tree[i].id=i;

         scanf("%d%d%d",&k,&p[i],&b);

         link(&tree[i],&tree[p[i]],k,b);

     }

     scanf("%d",&q);

     char ch[];

     int x,y,z,w;

     while(q--){

         scanf("%s",ch);

         if(ch[]=='A'){

             scanf("%d",&x);

             printf("%d\n",query(&tree[x]));

         }

         else{

             scanf("%d%d%d%d",&x,&y,&z,&w);

             cut(&tree[x]);p[x]=z;

             link(&tree[x],&tree[p[x]],y,w);

         }

     }

     return ;

 }