【POJ】3237 Tree

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<queue>
  4 #include<iostream>
  5 #include<algorithm>
  6 #define MAXN 100010
  7 #define MAXM 200010
  8 #define oo 0x7FFFFFFF
  9 using namespace std;
 10 bool vis[MAXN];
 11 int first[MAXN], next[MAXM], v[MAXM], cost[MAXM], e;
 12 struct LCT {
 13     bool neg[MAXN];
 14     int maxi[MAXN], mini[MAXN];
 15     int bef[MAXN], belong[MAXN];
 16     int next[MAXN][2], pre[MAXN], key[MAXN];
 17     void Init() {
 18         memset(next, 0, sizeof(next));
 19         memset(pre, 0, sizeof(pre));
 20         memset(neg, false, sizeof(neg));
 21         maxi[0] = -oo;
 22         mini[0] = oo;
 23     }
 24     inline void PushUp(int x) {
 25         maxi[x] = key[x];
 26         if (next[x][0])
 27             maxi[x] = max(maxi[x], maxi[next[x][0]]);
 28         if (next[x][1])
 29             maxi[x] = max(maxi[x], maxi[next[x][1]]);
 30         mini[x] = key[x];
 31         if (next[x][0])
 32             mini[x] = min(mini[x], mini[next[x][0]]);
 33         if (next[x][1])
 34             mini[x] = min(mini[x], mini[next[x][1]]);
 35     }
 36     inline void Not(int x) {
 37         if (x) {
 38             neg[x] ^= true;
 39             swap(maxi[x], mini[x]);
 40             key[x] = -key[x];
 41             maxi[x] = -maxi[x];
 42             mini[x] = -mini[x];
 43         }
 44     }
 45     inline void PushDown(int x) {
 46         if (neg[x]) {
 47             Not(next[x][0]);
 48             Not(next[x][1]);
 49             neg[x] = false;
 50         }
 51     }
 52     void Rotate(int x, int kind) {
 53         int y, z;
 54         y = pre[x];
 55         z = pre[y];
 56         PushDown(y);
 57         PushDown(x);
 58         next[y][!kind] = next[x][kind];
 59         pre[next[x][kind]] = y;
 60         next[z][next[z][1] == y] = x;
 61         pre[x] = z;
 62         next[x][kind] = y;
 63         pre[y] = x;
 64         PushUp(y);
 65     }
 66     void Splay(int x) {
 67         int rt;
 68         for (rt = x; pre[rt]; rt = pre[rt])
 69             ;
 70         if (rt != x) {
 71             bef[x] = bef[rt];
 72             bef[rt] = 0;
 73             PushDown(x);
 74             while (pre[x]) {
 75                 if (next[pre[x]][0] == x)
 76                     Rotate(x, 1);
 77                 else
 78                     Rotate(x, 0);
 79             }
 80             PushUp(x);
 81         }
 82     }
 83     void Access(int x) {
 84         int father;
 85         for (father = 0; x; x = bef[x]) {
 86             Splay(x);
 87             PushDown(x);
 88             pre[next[x][1]] = 0;
 89             bef[next[x][1]] = x;
 90             next[x][1] = father;
 91             pre[father] = x;
 92             bef[father] = 0;
 93             father = x;
 94             PushUp(x);
 95         }
 96     }
 97     void Change(int x, int y) {
 98         int t;
 99         t = belong[x - 1];
100         Splay(t);
101         key[t] = y;
102     }
103     void Negate(int x, int y) {
104         Access(y);
105         for (y = 0; x; x = bef[x]) {
106             Splay(x);
107             if (!bef[x]) {
108                 Not(y);
109                 Not(next[x][1]);
110                 return;
111             }
112             PushDown(x);
113             pre[next[x][1]] = 0;
114             bef[next[x][1]] = x;
115             next[x][1] = y;
116             pre[y] = x;
117             bef[y] = 0;
118             y = x;
119             PushUp(x);
120         }
121     }
122     int Query(int x, int y) {
123         Access(y);
124         for (y = 0; x; x = bef[x]) {
125             Splay(x);
126             if (!bef[x])
127                 return max(maxi[y], maxi[next[x][1]]);
128             PushDown(x);
129             pre[next[x][1]] = 0;
130             bef[next[x][1]] = x;
131             next[x][1] = y;
132             pre[y] = x;
133             bef[y] = 0;
134             y = x;
135             PushUp(x);
136         }
137         return 0;
138     }
139 } lct;
140 int INT() {
141     char ch;
142     int res;
143     bool neg;
144     while (ch = getchar(), !isdigit(ch) && ch != '-')
145         ;
146     if (ch == '-') {
147         res = 0;
148         neg = true;
149     } else {
150         res = ch - '0';
151         neg = false;
152     }
153     while (ch = getchar(), isdigit(ch))
154         res = res * 10 + ch - '0';
155     return neg ? -res : res;
156 }
157 char CHAR() {
158     char ch, res;
159     while (res = getchar(), !isalpha(res))
160         ;
161     while (ch = getchar(), isalpha(ch))
162         ;
163     return res;
164 }
165 inline void AddEdge(int x, int y, int val) {
166     v[e] = y;
167     cost[e] = val;
168     next[e] = first[x];
169     first[x] = e++;
170 }
171 void BFS(int x) {
172     int i, y;
173     queue<int> q;
174     memset(vis, false, sizeof(vis));
175     vis[x] = true;
176     q.push(x);
177     while (!q.empty()) {
178         x = q.front();
179         q.pop();
180         for (i = first[x]; i != -1; i = next[i]) {
181             y = v[i];
182             if (!vis[y]) {
183                 lct.bef[y] = x;
184                 lct.key[y] = cost[i];
185                 lct.belong[i >> 1] = y;
186                 vis[y] = true;
187                 q.push(y);
188             }
189         }
190     }
191 }
192 int main() {
193     int c, i;
194     char ch;
195     int n, x, y, val;
196     c = INT();
197     while (c--) {
198         n = INT();
199         lct.Init();
200         memset(first, -1, sizeof(first));
201         for (e = 0, i = 1; i < n; i++) {
202             x = INT(), y = INT(), val = INT();
203             AddEdge(x, y, val);
204             AddEdge(y, x, val);
205         }
206         BFS(1);
207         while (ch = CHAR(), ch != 'D') {
208             x = INT(), y = INT();
209             if (ch == 'Q')
210                 printf("%d\n", lct.Query(x, y));
211             else if (ch == 'C')
212                 lct.Change(x, y);
213             else
214                 lct.Negate(x, y);
215         }
216     }
217     return 0;
218 }