【HDU】3966 Aragorn's Story

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