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