HDU 3966 Aragorn's Story

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 const int maxn = 50010;
  4 struct node{
  5     int lt,rt,val,lazy;
  6 }tree[maxn<<2];
  7 int n,m,p,val[maxn],fa[maxn],top[maxn],de[maxn];
  8 int loc[maxn],siz[maxn],son[maxn],clk;
  9 vector<int>g[maxn];
 10 void FindHeavyEdge(int u,int father,int depth){
 11     fa[u] = father;
 12     de[u] = depth;
 13     son[u] = -1;
 14     siz[u] = 1;
 15     for(int i = g[u].size()-1; i >= 0; --i){
 16         if(g[u][i] == father) continue;
 17         FindHeavyEdge(g[u][i],u,depth + 1);
 18         siz[u] += siz[g[u][i]];
 19         if(son[u] == -1 || siz[g[u][i]] > siz[son[u]])
 20             son[u] = g[u][i];
 21     }
 22 }
 23 
 24 void build(int lt,int rt,int v){
 25     tree[v].lt = lt;
 26     tree[v].rt = rt;
 27     tree[v].lazy = tree[v].val = 0;
 28     if(lt == rt) return;
 29     int mid = (lt + rt)>>1;
 30     build(lt,mid,v<<1);
 31     build(mid + 1,rt,v<<1|1);
 32 }
 33 void pushdown(int v){
 34     if(tree[v].lazy){
 35         tree[v<<1].lazy += tree[v].lazy;
 36         tree[v<<1|1].lazy += tree[v].lazy;
 37         tree[v<<1].val += (tree[v<<1].rt - tree[v<<1].lt + 1)*tree[v].lazy;
 38         tree[v<<1|1].val += (tree[v<<1|1].rt - tree[v<<1|1].lt + 1)*tree[v].lazy;
 39         tree[v].lazy = 0;
 40     }
 41 }
 42 void update(int lt,int rt,int val,int v){
 43     if(lt <= tree[v].lt && rt >= tree[v].rt){
 44         tree[v].lazy += val;
 45         tree[v].val += (tree[v].rt - tree[v].lt + 1)*val;
 46         return;
 47     }
 48     pushdown(v);
 49     if(lt <= tree[v<<1].rt) update(lt,rt,val,v<<1);
 50     if(rt >= tree[v<<1|1].lt) update(lt,rt,val,v<<1|1);
 51 }
 52 void modify(int u,int v,int val){
 53     while(top[u] != top[v]){
 54         if(de[top[u]] < de[top[v]]) swap(u,v);
 55         update(loc[top[u]],loc[u],val,1);
 56         u = fa[top[u]];
 57     }
 58     if(de[u] > de[v]) swap(u,v);
 59     update(loc[u],loc[v],val,1);
 60 }
 61 int query(int pos,int v){
 62     if(tree[v].lt == tree[v].rt) return tree[v].val;
 63     pushdown(v);
 64     if(pos <= tree[v<<1].rt) return query(pos,v<<1);
 65     else return query(pos,v<<1|1);
 66 }
 67 void ConnectHeavyEdge(int u,int ancestor){
 68     top[u] = ancestor;
 69     loc[u] = clk++;
 70     if(son[u] != -1) ConnectHeavyEdge(son[u],ancestor);
 71     for(int i = g[u].size()-1; i >= 0; --i){
 72         if(g[u][i] == fa[u] || son[u] == g[u][i]) continue;
 73         ConnectHeavyEdge(g[u][i],g[u][i]);
 74     }
 75 }
 76 int main(){
 77     int u,v,w;
 78     while(~scanf("%d%d%d",&n,&m,&p)){
 79         for(int i = 0; i < maxn; ++i) g[i].clear();
 80         for(int i = 1; i <= n; ++i) scanf("%d",val + i);
 81         for(int i = clk = 0; i < m; ++i){
 82             scanf("%d%d",&u,&v);
 83             g[u].push_back(v);
 84             g[v].push_back(u);
 85         }
 86         FindHeavyEdge(1,0,0);
 87         ConnectHeavyEdge(1,1);
 88         build(0,clk-1,1);
 89         for(int i = 1; i <= n; ++i) update(loc[i],loc[i],val[i],1);
 90         char op[10];
 91         while(p--){
 92             scanf("%s",op);
 93             if(op[0] == ‘I‘){
 94                 scanf("%d%d%d",&u,&v,&w);
 95                 modify(u,v,w);
 96             }else if(op[0] == ‘D‘){
 97                 scanf("%d%d%d",&u,&v,&w);
 98                 modify(u,v,-w);
 99             }else if(op[0] == ‘Q‘){
100                 scanf("%d",&u);
101                 printf("%d\n",query(loc[u],1));
102             }
103         }
104     }
105     return 0;
106 }