SPOJ 375. 동적 트리

375. Query on a tree Problem code: QTREE
 
You are given a tree (an acyclic undirected connected graph) with N nodes, and edges numbered 1, 2, 3...N-1.
We will ask you to perfrom some instructions of the following form:

CHANGE i ti : change the cost of the i-th edge to tior

QUERY a b : ask for the maximum edge cost on the path from node a to node b

Input
The first line of input contains an integer t, the number of test cases (t <= 20). t test cases follow.
For each test case:

In the first line there is an integer N (N <= 10000),

In the next N-1 lines, the i-th line describes the i-th edge: a line with three integers a b c denotes an edge between a, b of cost c (c <= 1000000),

The next lines contain instructions "CHANGE i ti" or "QUERY a b",

The end of each test case is signified by the string "DONE".

There is one blank line between successive tests.
Output
For each "QUERY"operation, write one integer representing its result.
Example

Input:
1

3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE

Output:
1
3

 
 

  1 /* ***********************************************
  2 Author        :kuangbin
  3 Created Time  :2013-9-3 21:06:05
  4 File Name     :F:\2013ACM  \    \   -LCT\SPOJQTREE.cpp
  5 ************************************************ */
  6 
  7 #include <stdio.h>
  8 #include <string.h>
  9 #include <iostream>
 10 #include <algorithm>
 11 #include <vector>
 12 #include <queue>
 13 #include <set>
 14 #include <map>
 15 #include <string>
 16 #include <math.h>
 17 #include <stdlib.h>
 18 #include <time.h>
 19 using namespace std;
 20 
 21 //    ，      ：
 22 //1.    
 23 //2.  u->v         
 24 const int MAXN = 10010;
 25 int ch[MAXN][2],pre[MAXN];
 26 int Max[MAXN],key[MAXN];
 27 bool rt[MAXN];
 28 void push_down(int r)
 29 {
 30     
 31 }
 32 void push_up(int r)
 33 {
 34     Max[r] = max(max(Max[ch[r][0]],Max[ch[r][1]]),key[r]);
 35 }
 36 void Rotate(int x)
 37 {
 38     int y = pre[x], kind = ch[y][1]==x;
 39     ch[y][kind] = ch[x][!kind];
 40     pre[ch[y][kind]] = y;
 41     pre[x] = pre[y];
 42     pre[y] = x;
 43     ch[x][!kind] = y;
 44     if(rt[y])
 45         rt[y] = false, rt[x] = true;
 46     else 
 47         ch[pre[x]][ch[pre[x]][1]==y] = x;
 48     push_up(y);
 49 }
 50 void P(int r)
 51 {
 52     if(!rt[r])P(pre[r]);
 53     push_down(r);
 54 }
 55 void Splay(int r)
 56 {
 57     //P(r);
 58     while( !rt[r] )
 59     {
 60         int f = pre[r], ff = pre[f];
 61         if(rt[f])
 62             Rotate(r);
 63         else if( (ch[ff][1]==f)==(ch[f][1]==r) )
 64             Rotate(f), Rotate(r);
 65         else
 66             Rotate(r), Rotate(r);
 67     }
 68     push_up(r);
 69 }
 70 int Access(int x)
 71 {
 72     int y = 0;
 73     do
 74     {
 75         Splay(x);
 76         rt[ch[x][1]] = true, rt[ch[x][1]=y] = false;
 77         push_up(x);
 78         x = pre[y=x];
 79     }
 80     while(x);
 81     return y;
 82 }
 83 //   u   u v lca,v ch[u][1]    lca 2   
 84 //(  u v   2   )
 85 void lca(int &u,int &v)
 86 {
 87     Access(v), v = 0;
 88     while(u)
 89     {
 90         Splay(u);
 91         if(!pre[u])return;
 92         rt[ch[u][1]] = true;
 93         rt[ch[u][1]=v] = false;
 94         push_up(u);
 95         u = pre[v = u];
 96     }
 97 }
 98 
 99 void change(int u,int k)
100 {
101     Access(u);
102     key[u] = k;
103     push_up(u);
104 }
105 void query(int u,int v)
106 {
107     lca(u,v);
108     printf("%d
",max(Max[v],Max[ch[u][1]]));
109 }
110 
111 struct Edge
112 {
113     int to,next;
114     int val;
115     int index;
116 }edge[MAXN*2];
117 int head[MAXN],tot;
118 int id[MAXN];
119 
120 void addedge(int u,int v,int val,int index)
121 {
122     edge[tot].to = v;
123     edge[tot].next = head[u];
124     edge[tot].val = val;
125     edge[tot].index = index;
126     head[u] = tot++;
127 }
128 void dfs(int u)
129 {
130     for(int i = head[u];i != -1;i = edge[i].next)
131     {
132         int v = edge[i].to;
133         if(pre[v] != 0)continue;
134         pre[v] = u;
135         id[edge[i].index] = v;
136         key[v] = edge[i].val;
137         dfs(v);
138     }
139 }
140 void init()
141 {
142     tot = 0;
143     memset(head,-1,sizeof(head));
144 }
145 int main()
146 {
147     //freopen("in.txt","r",stdin);
148     //freopen("out.txt","w",stdout);
149     int T;
150     int n;
151     int u,v,w;
152     char op[20];
153     scanf("%d",&T);
154     while(T--)
155     {
156         init();
157         scanf("%d",&n);
158         for(int i = 0;i <= n;i++)
159         {
160             pre[i] = 0;
161             ch[i][0] = ch[i][1] = 0;
162             rt[i] = true;
163         }
164         Max[0] = -2000000000;
165         for(int i = 1;i < n;i++)
166         {
167             scanf("%d%d%d",&u,&v,&w);
168             addedge(u,v,w,i);
169             addedge(v,u,w,i);
170         }
171         pre[1] = -1;
172         dfs(1);
173         pre[1] = 0;
174         while(scanf("%s",&op) == 1)
175         {
176             if(op[0] == 'D')break;
177             scanf("%d%d",&u,&v);
178             if(op[0] == 'C')
179                 change(id[u],v);
180             else query(u,v);
181         }
182     }
183     return 0;
184 }