加long long
不开long long 见祖宗！！！
by _Agony @ 2021-09-04 08:53:49
```
#include <iostream>
#include <cstdio>
#define ll long long
//#define int long long
using namespace std;
const int N = 4e5;
int n, m;
ll a[N];
ll re() {
ll x = 0, f = 1;
char ch = getchar();
while(ch < '0'||ch > '9') {
if(ch == '-') f = -1;
ch = getchar();
}
while (ch <= '9'&&ch >= '0') {
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
int cnt;
int head[N<<2];
struct bal {
int nxt;
int to;
};
bal e[N<<1];
void add(int u, int v) {
++cnt;
e[cnt].nxt = head[u];
e[cnt].to = v;
head[u] = cnt;
}
int fa[N];
ll tot[N];
int son[N];
int dep[N];
void dfs1(int x, int f, int deep) {
dep[x] = deep;
tot[x] = 1;
fa[x] = f;
for(int i = head[x]; i; i = e[i].nxt) {
int v = e[i].to;
if(v == f) continue;
dfs1(v, x, deep + 1);
if(tot[v] > tot[son[x]])
son[x] = v;
tot[x] += tot[v];
}
}
int num;
int b[N];
int top[N];
ll idx[N];
void dfs2(int x, int ftop) {
top[x] = ftop;
idx[x] = ++num;
b[num] = a[x];
if(son[x]) dfs2(son[x], ftop);
for(int i = head[x]; i; i = e[i].nxt) {
int v = e[i].to;
if(v == fa[x]||v == son[x])
continue;
dfs2(v, v);
}
}
struct ball {
int l, r;
int size;
ll lazy;
ll sum;
};
ball t[N<<2];
void update(int k) {
t[k].sum = t[k<<1].sum + t[k<<1|1].sum;
}
void build(ll p, int l, int r) {
if(l <= 0||r > n||l > r) return ;
t[p].l = l; t[p].r = r;
t[p].size = r - l + 1;
if(l == r) {
t[p].sum = b[l];
return ;
}
int mid = (l + r) >> 1;
build(p<<1, l, mid);
build(p<<1|1, mid + 1, r);
update(p);
}
void pushdown(ll p) {
if(!t[p].lazy) return ;
t[p<<1].sum += (ll)t[p<<1].size * t[p].lazy;
t[p<<1|1].sum += (ll)t[p<<1|1].size * t[p].lazy;
t[p<<1].lazy += (ll)t[p].lazy;
t[p<<1|1].lazy += (ll)t[p].lazy;
t[p].lazy = 0;
}
void Tree_addition(ll p, int l, int r, ll val) {
if(l > r||l < 0||r > n) return ;
if(t[p].l >= l&&t[p].r <= r) {
t[p].sum += (1ll) * (t[p].size * val);
t[p].lazy += (ll)val;
return ;
}
int mid = (t[p].l + t[p].r)>>1;
pushdown(p);
if(mid >= l) Tree_addition(p<<1, l, r, val);
if(mid < r) Tree_addition(p<<1|1, l, r, val);
update(p);
return ;
}
ll Tree_sum(ll p, int l, int r) {
if(t[p].l >= l&&t[p].r <= r)
return (ll)t[p].sum;
pushdown(p);
ll ans = 0;
int mid = (t[p].l + t[p].r) >> 1;
if(mid >= l) ans += (ll)Tree_sum(p<<1, l, r);
if(mid < r) ans += (ll)Tree_sum(p<<1|1, l, r);
return ans;
}
void Interval_sum(int x, int y) {
ll ans = 0;
while (top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]])
swap(x, y);
ans += Tree_sum(1, idx[top[x]], idx[x]);
x = fa[top[x]];
}
if(dep[x] < dep[y]) swap(x, y);
ans += Tree_sum(1, idx[y], idx[x]);
printf("%lld\n", ans);
}
signed main() {
// freopen("P3178_1.in", "r", stdin);
// freopen("dsd.out", "w", stdout);
int u, v, op;
n = re(); m = re();
for(int i = 1; i <= n; i++)
a[i] = re();
for(int i = 1; i < n; i++) {
scanf("%d%d", &u,&v);
add(u, v); add(v, u);
}
dfs1(1, 0, 1);
dfs2(1, 1);
build(1, 1, n);
for(int i = 1; i <= m; i++) {
op = re(); u = re();
if(op == 1) {
v = re();
Tree_addition(1, idx[u], idx[u], v);
}
if(op == 2) {
v = re();
Tree_addition(1, idx[u], idx[u] + tot[u] - 1, v);
}
if(op == 3)
Interval_sum(1, u);
}
return 0;
}
```
by _Agony @ 2021-09-04 08:54:08