BZOJ 4034——[HAOI 2015]T 2
1、テーマの大意:ツリーのポイント修正とツリー修正、ツリーパスと
2、分析:木の鎖はヌード問題を切り開きます.
2、分析:木の鎖はヌード問題を切り開きます.
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define M 1000000
#define LL long long
LL Size[M], value[M], Top[M], Fa[M], Height[M], num[M], left[M], right[M];
LL tot, ST_tot;
LL son[M], head[M], Next[M];
LL n, m;
LL q[M], lazy[M];
void init(){
memset(head, -1, sizeof(head));
memset(lazy, 0, sizeof(lazy));
tot = ST_tot = 0;
Top[1] = 1;
}
void pushdown(LL l, LL r, LL o){
LL mid = (l + r) / 2;
q[2 * o] += (mid + 1 - l) * lazy[o];
q[2 * o + 1] += (r - mid) * lazy[o];
lazy[2 * o] += lazy[o];
lazy[2 * o + 1] += lazy[o];
lazy[o] = 0;
}
void add(LL l, LL r, LL o, LL x, LL y, LL z){
if(x <= l && r <= y){
lazy[o] += z;
q[o] += (r - l + 1) * z;
return;
}
pushdown(l, r, o);
LL mid = (l + r) / 2;
if(x <= mid) add(l, mid, 2 * o, x, y, z);
if(y > mid) add(mid + 1, r, 2 * o + 1, x, y, z);
q[o] = q[2 * o] + q[2 * o + 1];
}
LL query(LL l, LL r, LL o, LL x, LL y){
if(x <= l && r <= y) return q[o];
pushdown(l, r, o);
LL mid = (l + r) / 2, ret = 0;
if(x <= mid) ret += query(l, mid, 2 * o, x, y);
if(y > mid) ret += query(mid + 1, r, 2 * o + 1, x, y);
return ret;
}
void insert(LL x, LL y){
tot ++;
son[tot] = y;
Next[tot] = head[x];
head[x] = tot;
}
void dfs1(LL x, LL fa, LL height){
Fa[x] = fa;
Height[x] = height;
Size[x] = 1;
for(LL i = head[x]; i != -1; i = Next[i]) if(son[i] != fa){
dfs1(son[i], x, height + 1);
Size[x] += Size[son[i]];
}
}
void dfs2(LL x, LL fa){
++ ST_tot;
left[x] = ST_tot;
num[x] = ST_tot;
add(1, n, 1, ST_tot, ST_tot, value[x]);
LL o = 0, ss = 0;
for(LL i = head[x]; i != -1; i = Next[i]) if(son[i] != fa){
if(Size[son[i]] > ss){
ss = Size[son[i]];
o = i;
}
}
if(o != 0){
Top[son[o]] = Top[x];
dfs2(son[o], x);
}
for(LL i = head[x]; i != -1; i = Next[i]) if(son[i] != fa && o != i){
Top[son[i]] = son[i];
dfs2(son[i], x);
}
right[x] = ST_tot;
}
void real_add(LL x, LL y){
add(1, n, 1, left[x], right[x], y);
}
void real_add1(LL x, LL y){
add(1, n, 1, num[x], num[x], y);
}
LL real_query(LL x){
LL y = 1;
LL ret = 0;
while(Top[x] != Top[y]){
if(Height[Top[x]] < Height[Top[y]]) swap(x, y);
ret += query(1, n, 1, num[Top[x]], num[x]);
x = Fa[Top[x]];
}
if(Height[x] < Height[y]) swap(x, y);
ret += query(1, n, 1, num[y], num[x]);
return ret;
}
int main(){
scanf("%lld%lld", &n, &m);
for(LL i = 1; i <= n; i ++) scanf("%lld", &value[i]);
init();
for(LL i = 1; i < n; i ++){
LL x, y;
scanf("%lld%lld", &x, &y);
insert(x, y);
insert(y, x);
}
dfs1(1, 0, 1);
dfs2(1, 0);
for(LL i = 1; i <= m; i ++){
LL op, x, a;
scanf("%lld", &op);
if(op == 1){
scanf("%lld%lld", &x, &a);
real_add1(x, a);
}
else if(op == 2){
scanf("%lld%lld", &x, &a);
real_add(x, a);
}
else{
scanf("%lld", &x);
printf("%lld
", real_query(x));
}
}
return 0;
}