【SPOJ】375 Query on a tree

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<queue>
  4 #include<iostream>
  5 #include<algorithm>
  6 #define MAXN 10010
  7 #define MAXM 20010
  8 #define oo 0x7FFFFFFF
  9 using namespace std;
 10 int first[MAXN], next[MAXM], v[MAXM], cost[MAXM], e;
 11 bool vis[MAXN];
 12 struct LCT {
 13     int next[MAXN][2], pre[MAXN], val[MAXN], belong[MAXN], bef[MAXN], key[MAXN];
 14     void Init() {
 15         memset(next, 0, sizeof(next));
 16         memset(pre, 0, sizeof(pre));
 17         val[0] = key[0] = -oo;
 18     }
 19     inline void PushUp(int x) {
 20         val[x] = max(key[x], max(val[next[x][0]], val[next[x][1]]));
 21     }
 22     inline void Rotate(int x, int kind) {
 23         int y, z;
 24         y = pre[x];
 25         z = pre[y];
 26         next[y][!kind] = next[x][kind];
 27         pre[next[x][kind]] = y;
 28         next[z][next[z][1] == y] = x;
 29         pre[x] = z;
 30         next[x][kind] = y;
 31         pre[y] = x;
 32         PushUp(y);
 33     }
 34     void Splay(int x) {
 35         int rt;
 36         for (rt = x; pre[rt]; rt = pre[rt])
 37             ;
 38         if (rt != x) {
 39             bef[x] = bef[rt];
 40             bef[rt] = 0;
 41             while (pre[x]) {
 42                 if (next[pre[x]][0] == x)
 43                     Rotate(x, 1);
 44                 else
 45                     Rotate(x, 0);
 46             }
 47             PushUp(x);
 48         }
 49     }
 50     void Access(int x) {
 51         int father;
 52         for (father = 0; x; x = bef[x]) {
 53             Splay(x);
 54             bef[next[x][1]] = x;
 55             bef[father] = 0;
 56             pre[next[x][1]] = 0;
 57             next[x][1] = father;
 58             pre[father] = x;
 59             father = x;
 60             PushUp(x);
 61         }
 62     }
 63     int Query(int x, int y) {
 64         Access(y);
 65         for (y = 0; x; x = bef[x]) {
 66             Splay(x);
 67             if (!bef[x])
 68                 return max(val[y], val[next[x][1]]);
 69             bef[next[x][1]] = x;
 70             bef[y] = 0;
 71             pre[next[x][1]] = 0;
 72             next[x][1] = y;
 73             pre[y] = x;
 74             y = x;
 75             PushUp(x);
 76         }
 77         return 0;
 78     }
 79     void Change(int x, int y) {
 80         int t;
 81         t = belong[x - 1];
 82         key[t] = y;
 83         Splay(t);
 84     }
 85 } lct;
 86 int INT() {
 87     int res;
 88     char ch;
 89     bool neg;
 90     while (ch = getchar(), !isdigit(ch) && ch != '-')
 91         ;
 92     if (ch == '-') {
 93         neg = true;
 94         res = 0;
 95     } else {
 96         neg = false;
 97         res = ch - '0';
 98     }
 99     while (ch = getchar(), isdigit(ch))
100         res = res * 10 + ch - '0';
101     return neg ? -res : res;
102 }
103 char CHAR() {
104     char res, ch;
105     while (res = getchar(), !isalpha(res))
106         ;
107     while (ch = getchar(), isalpha(ch))
108         ;
109     return res;
110 }
111 inline void AddEdge(int x, int y, int val) {
112     v[e] = y;
113     cost[e] = val;
114     next[e] = first[x];
115     first[x] = e++;
116 }
117 void BFS(int x) {
118     int i, y;
119     queue<int> q;
120     memset(vis, false, sizeof(vis));
121     vis[x] = true;
122     q.push(x);
123     while (!q.empty()) {
124         x = q.front();
125         q.pop();
126         for (i = first[x]; i != -1; i = next[i]) {
127             y = v[i];
128             if (!vis[y]) {
129                 lct.bef[y] = x;
130                 lct.key[y] = lct.val[y] = cost[i];
131                 lct.belong[i >> 1] = y;
132                 vis[y] = true;
133                 q.push(y);
134             }
135         }
136     }
137 }
138 int main() {
139     int c;
140     char ch;
141     int n, i;
142     int u, v, w;
143     c = INT();
144     while (c--) {
145         lct.Init();
146         n = INT();
147         memset(first, -1, sizeof(first));
148         for (e = 0, i = 1; i < n; i++) {
149             u = INT(), v = INT(), w = INT();
150             AddEdge(u, v, w);
151             AddEdge(v, u, w);
152         }
153         BFS(1);
154         while (ch = CHAR(), ch != 'D') {
155             u = INT(), v = INT();
156             if (ch == 'Q')
157                 printf("%d\n", lct.Query(u, v));
158             else
159                 lct.Change(u, v);
160         }
161     }
162     return 0;
163 }