动态树(Link Cut Tree) ：SPOJ 375 Query on a tree

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 
  5 using namespace std;
  6 const int maxn=10010;
  7 int Max[maxn],fa[maxn],ch[maxn][2],key[maxn];
  8 bool rt[maxn];
  9 
 10 void Push_up(int p)
 11 {
 12     Max[p]=max(key[p],max(Max[ch[p][0]],Max[ch[p][1]]));
 13 }
 14 
 15 void Rotate(int x)
 16 {
 17     int y=fa[x],g=fa[y],c=ch[y][1]==x;
 18     ch[y][c]=ch[x][c^1];ch[x][c^1]=y;
 19     fa[ch[y][c]]=y;fa[y]=x;fa[x]=g;
 20     if(rt[y])
 21         rt[y]=false,rt[x]=true;
 22     else
 23         ch[g][ch[g][1]==y]=x;
 24     Push_up(y);        
 25 }
 26 
 27 void Splay(int x)
 28 {
 29     for(int y=fa[x];!rt[x];Rotate(x),y=fa[x])
 30         if(!rt[y])
 31             Rotate((ch[fa[y]][1]==y)==(ch[y][1]==x)?y:x);
 32     Push_up(x);
 33 }
 34 
 35 void Access(int x)
 36 {
 37     int y=0;
 38     while(x){
 39         Splay(x);
 40         rt[ch[x][1]]=true;
 41         rt[ch[x][1]=y]=false;
 42         Push_up(x);
 43         x=fa[y=x];
 44     }
 45 }
 46 
 47 void Query(int x,int y)
 48 {
 49     Access(y),y=0;
 50     while(true)
 51     {
 52         Splay(x);
 53         if(!fa[x]){
 54             printf("%d\n",max(Max[y],Max[ch[x][1]]));
 55             return;
 56         }
 57         rt[ch[x][1]]=true;
 58         rt[ch[x][1]=y]=false;
 59         Push_up(x);
 60         x=fa[y=x];        
 61     }
 62 }
 63 
 64 void Change(int x,int d)
 65 {
 66     Access(x);
 67     Splay(x);
 68     key[x]=d;
 69     Push_up(x);
 70 }
 71 
 72 int fir[maxn],nxt[maxn<<1],to[maxn<<1],cnt;
 73 int e[maxn][3];
 74 
 75 void addedge(int a,int b)
 76 {
 77     nxt[++cnt]=fir[a];to[cnt]=b;fir[a]=cnt;
 78 }
 79 
 80 void DFS(int node)
 81 {
 82     for(int i=fir[node];i;i=nxt[i])
 83     {
 84         if(fa[to[i]])continue;
 85         fa[to[i]]=node;
 86         DFS(to[i]);
 87     }
 88 }
 89 
 90 void Init()
 91 {
 92     cnt=0;Max[0]=-1000000000;
 93     for(int i=1;i<=10000;i++){
 94         Max[i]=fir[i]=fa[i]=0;
 95         rt[i]=1;
 96     }
 97     return;
 98 }
 99 int main()
100 {
101     int T,n,a,b;
102     scanf("%d",&T);
103     while(T--)
104     {
105         Init();
106         scanf("%d",&n);
107         for(int i=1;i<n;i++)
108             scanf("%d%d%d",&e[i][0],&e[i][1],&e[i][2]);
109         for(int i=1;i<n;i++)
110             addedge(e[i][0],e[i][1]),addedge(e[i][1],e[i][0]);
111         fa[1]=-1;
112         DFS(1);
113         fa[1]=0;
114         for(int i=1;i<n;i++)
115         {
116             if(fa[e[i][0]]==e[i][1])
117                 swap(e[i][0],e[i][1]);
118             Change(e[i][1],e[i][2]);
119         }    
120         char op[10];
121         while(true)
122         {
123             scanf("%s",op);
124             if(!strcmp(op,"DONE"))break;
125             else if(!strcmp(op,"QUERY")){
126                 scanf("%d%d",&a,&b);
127                 Query(a,b);
128             }
129                 
130             else {
131                 scanf("%d%d",&a,&b);
132                 Change(e[a][1],b);
133             }
134         }    
135     }
136     
137     return 0;
138 }