HDU 3966 RE 树链剖分 Aragorn's Story

                  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <vector>
  6usingnamespace std;
  7  8constint maxn = 50000 + 10;
  9constint INF = 0x3f3f3f3f;
 10 11void scan(int& x)
 12{
 13     x = 0;
 14bool flag = false;
 15char c = ‘‘;
 16while(c != ‘-‘ && (c < ‘0‘ || c > ‘9‘)) c = getchar();
 17if(c == ‘-‘) { flag = true; c = getchar(); }
 18while(c >= ‘0‘ && c <= ‘9‘) { x = x * 10 + c - ‘0‘; c = getchar(); }
 19if(flag) x = -x;
 20}
 21 22int n, m, Q;
 23 24 vector<int> G[maxn];
 25int val[maxn];
 26 27int tot;
 28int L[maxn];
 29int fa[maxn];
 30int id[maxn];
 31int top[maxn];
 32int sz[maxn];
 33int son[maxn];
 34 35void dfs(int u)
 36{
 37     sz[u] = 1;
 38     son[u] = 0;
 39for(int i = 0; i < G[u].size(); i++)
 40    {
 41int v = G[u][i];
 42if(v == fa[u]) continue;
 43         fa[v] = u;
 44         L[v] = L[u] + 1;
 45        dfs(v);
 46         sz[u] += sz[v];
 47if(sz[v] > sz[son[u]]) son[u] = v;
 48    }
 49}
 50 51void dfs2(int u, int tp)
 52{
 53     top[u] = tp;
 54     id[u] = ++tot;
 55if(son[u]) dfs2(son[u], tp);
 56for(int i = 0; i < G[u].size(); i++)
 57    {
 58int v = G[u][i];
 59if(v == fa[u] || v == son[u]) continue;
 60        dfs2(v, v);
 61    }
 62}
 63 64int vv;
 65int add[maxn << 2];
 66 67void update(int o, int L, int R, int qL, int qR)
 68{
 69if(qR < L || qL > R) return ;
 70if(qL <= L && R <= qR) { add[o] += vv; return ; }
 71int M = (L + R) / 2;
 72     update(o<<1, L, M, qL, qR);
 73     update(o<<1|1, M+1, R, qL, qR);
 74}
 75 76int query(int o, int L, int R, int p)
 77{
 78if(L == R) return add[o];
 79int M = (L + R) / 2;
 80     add[o<<1] += add[o];
 81     add[o<<1|1] += add[o];
 82     add[o] = 0;
 83if(p <= M) return query(o<<1, L, M, p);
 84return query(o<<1|1, M+1, R, p);
 85}
 86 87void Update(int u, int v)
 88{
 89int t1 = top[u], t2 = top[v];
 90while(t1 != t2)
 91    {
 92if(L[t1] < L[t2]) { swap(t1, t2); swap(u, v); }
 93         update(1, 1, tot, id[t1], id[u]);
 94         u = fa[t1], t1 = top[u];
 95    }
 96if(u == v) return ;
 97if(L[u] < L[v]) swap(u, v);
 98     update(1, 1, tot, id[v], id[u]);
 99}
100101int main()
102{
103while(scanf("%d%d%d", &n, &m, &Q) == 3)
104    {
105for(int i = 1; i <= n; i++) { G[i].clear(); scan(val[i]); }
106for(int i = 1; i < n; i++)
107        {
108int u, v; scan(u); scan(v);
109            G[u].push_back(v); G[v].push_back(u);
110        }
111112         L[1] = fa[1] = 0;
113         dfs(1);
114         tot = 0;
115         dfs2(1, 1);
116117         memset(add, 0, sizeof(add));
118char op[10];
119while(Q--)
120        {
121int x, y;
122             scanf("%s", op);
123if(op[0] == ‘Q‘)
124            {
125                scan(x);
126                 printf("%d\n", val[x] + query(1, 1, tot, x));
127            }
128else129            {
130                scan(x); scan(y); scan(vv);
131if(op[0] == ‘D‘) vv = -vv;
132                Update(x, y);
133            }
134        }
135    }
136137return0;
138 }