P3833 [SHOI2012]魔法树

题目链接：https://www.luogu.org/problem/P3833

  1 #include <stdio.h>
  2 #include <algorithm>
  3 #include <iostream>
  4 #include <stdbool.h>
  5 #include <stdlib.h>
  6 #include <string>
  7 #include <string.h>
  8 #include <stack>
  9 #include <queue>
 10 #include <set>
 11 #include <map>
 12 #include <math.h>
 13 
 14 #define INF 0x3f3f3f3f
 15 #define LL long long
 16 using namespace std;
 17 
 18 const int maxn = 100050;
 19 
 20 struct Edge{
 21     int to,next;
 22 }edge[maxn*4];
 23 
 24 int head[maxn],tot;
 25 
 26 void add_edge(int u,int v){
 27     edge[tot] = Edge{v,head[u]};
 28     head[u] = tot++;
 29     //edge[tot] = Edge{u,head[v]};
 30     //head[v] = tot++;
 31 }
 32 
 33 int v[maxn];
 34 int fa[maxn];
 35 int siz[maxn];
 36 int dep[maxn];
 37 int son[maxn];
 38 
 39 void dfs1(int u,int f){
 40     fa[u] = f;
 41     dep[u] = dep[f] + 1;
 42     siz[u] = 1;
 43     int maxsize = -1;
 44     for (int i=head[u];~i;i=edge[i].next){
 45         int v = edge[i].to;
 46         if (v == f){
 47             continue;
 48         }
 49         dfs1(v,u);
 50         siz[u] += siz[v];
 51         if (siz[v] > maxsize){
 52             maxsize = siz[v];
 53             son[u] = v;
 54         }
 55     }
 56 }
 57 
 58 
 59 int tim;
 60 int dfn[maxn];
 61 int top[maxn];
 62 int w[maxn];
 63 
 64 void dfs2(int u,int t){
 65     dfn[u] = ++tim;
 66     top[u] = t;
 67     w[tim] = v[u];
 68     if (!son[u]){
 69         return ;
 70     }
 71     dfs2(son[u],t);
 72     for (int i=head[u];~i;i=edge[i].next){
 73         int v = edge[i].to;
 74         if (v == fa[u] || v == son[u]){
 75             continue;
 76         }
 77         dfs2(v,v);
 78     }
 79 }
 80 
 81 struct segment_tree{
 82     int l,r;
 83     LL val;
 84     int lazy;
 85 }tree[maxn*4];
 86 
 87 void pushup(int nod){
 88     tree[nod].val = (tree[nod<<1].val + tree[(nod<<1)+1].val);
 89 }
 90 
 91 void pushdown(int nod){
 92     tree[nod<<1].lazy += tree[nod].lazy;
 93     tree[(nod<<1)+1].lazy += tree[nod].lazy;
 94     tree[nod<<1].val += (tree[nod<<1].r-tree[nod<<1].l + 1) * tree[nod].lazy;
 95     tree[(nod<<1)+1].val += (tree[(nod<<1)+1].r-tree[(nod<<1)+1].l+1) * tree[nod].lazy;
 96     tree[nod].lazy = 0;
 97 }
 98 
 99 void build (int l,int r,int nod){
100     tree[nod].l = l;
101     tree[nod].r = r;
102     if (l == r){
103         tree[nod].lazy = 0;
104         tree[nod].val = w[l];
105         return ;
106     }
107     int mid = (l + r) >> 1;
108     build(l,mid,nod<<1);
109     build(mid+1,r,(nod<<1)+1);
110     pushup(nod);
111 }
112 
113 
114 void modify(int x,int y,int z,int k=1){
115     int l = tree[k].l, r = tree[k].r;
116     if (x <= l && y>=r){
117         tree[k].lazy += z;
118         tree[k].val += (r-l+1) * z;
119         return ;
120     }
121     if (tree[k].lazy){
122         pushdown(k);
123     }
124     int mid = (l + r) >> 1;
125     if (x <= mid){
126         modify(x,y,z,k<<1);
127     }
128     if (y > mid){
129         modify(x,y,z,(k<<1)+1);
130     }
131     pushup(k);
132 }
133 
134 LL query(int x,int y,int k=1){
135     int l = tree[k].l,r = tree[k].r;
136     if (x <= l && y >= r){
137         return tree[k].val;
138     }
139     if (tree[k].lazy){
140         pushdown(k);
141     }
142     int mid = (l + r) >> 1;
143     LL sum = 0;
144     if (x <= mid){
145         sum += query(x,y,k<<1);
146     }
147     if (y > mid){
148         sum += query(x,y,(k<<1)+1);
149     }
150     return sum;
151 }
152 
153 LL q_query(int x){
154     return query(dfn[x],dfn[x]+siz[x]-1);
155 }
156 
157 void mchain(int x,int y,int z) {
158     while (top[x] != top[y]) {
159         if (dep[top[x]] < dep[top[y]])
160             swap(x, y);
161         modify(dfn[top[x]], dfn[x], z);
162         x = fa[top[x]];
163     }
164     if (dep[x] > dep[y])
165         swap(x, y);
166     modify(dfn[x], dfn[y], z);
167 }
168 
169 
170 int main(){
171     int n;
172     scanf("%d",&n);
173     memset(head,-1, sizeof(head));
174     for (int i=1;i<=n-1;i++){
175         int x,y;
176         scanf("%d%d",&x,&y);
177         add_edge(x,y);
178     }
179     dfs1(0,0);
180     dfs2(0,0);
181     build(1,n,1);
182     int T;
183     scanf("%d",&T);
184     while (T--){
185         char s[4];
186         int x,y,z;
187         scanf("%s",s);
188         if (s[0] == ‘A‘){
189             scanf("%d%d%d",&x,&y,&z);
190             mchain(x,y,z);
191         }
192         if (s[0] == ‘Q‘) {
193             scanf("%d",&x);
194             printf("%lld\n",q_query(x));
195         }
196     }
197     return 0;
198 }