【HYSBZ】1036 树的统计Count

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