建议将size数组改为siz数组
by Ayin @ 2023-09-23 13:51:07
op==2的时候size-1
by LZMkingNB @ 2023-09-23 13:53:01
@[xiaozhuo](/user/355377)
1. 建议 `define` 一下 `long long` ，有地方少开了，我不知道是哪，但是加了 `#define int long long` 就可以过，不加就不行。
2. 同楼上，子树操作是 $\operatorname{dfn}[x]$ 到 $\operatorname{dfn}[x]+\operatorname{size[x]}-1$。
3. 操作 $3$，再特判一下 `if (op == 3) cout << qq(x, 1) << endl;`，不然会多输出。
### code:
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, dep[100010], head[100010], id[100010], rev[100010], top[100010], son[100010], fa[100010], cnt, m, tot, size[100010], w[100010];
struct Node
{
int to, next;
}e[200010];
long long tr[400010], tag[400010];
void add(int u ,int v)
{
e[++cnt].to = v, e[cnt].next = head[u], head[u] = cnt;
}
void dfs1(int u, int f)
{
dep[u] = dep[f] + 1;
fa[u] = f;
size[u] = 1;
for(int i = head[u];i;i = e[i].next)
{
int y = e[i].to;
if(y == f) continue;
dfs1(y, u);
size[u] += size[y];
if(size[y] > size[son[u]]) son[u] = y;
}
}
void dfs2(int u, int topf)
{
top[u] = topf;
id[u] = ++tot;
rev[tot] = w[u];
if(!son[u]) return;
dfs2(son[u], topf);
for(int i = head[u];i;i = e[i].next)
{
int y = e[i].to;
if(y == fa[u] || y == son[u]) continue;
dfs2(y, y);
}
}
void pushdown(int rt, int len)
{
if(tag[rt])
{
tag[rt * 2] += tag[rt];
tag[rt * 2 + 1] += tag[rt];
tr[rt * 2] += tag[rt] * (len - (len >> 1));
tr[rt * 2 + 1] += tag[rt] * (len >> 1);
tag[rt] = 0;
}
}
void build(int l, int r, int rt)
{
if(l == r)
{
tr[rt] = rev[l];
return;
}
int mid = (l + r) >> 1;
build(l, mid, rt * 2);
build(mid + 1, r, rt * 2 + 1);
tr[rt] = tr[rt * 2] + tr[rt * 2 + 1];
}
void update(int L, int R, int l, int r, int rt, int k)
{
if(L <= l && r <= R)
{
tr[rt] += k * (r - l + 1);
tag[rt] += k;
return;
}
pushdown(rt, r - l + 1);
int mid = (l + r) >> 1;
if(L <= mid) update(L, R, l, mid, rt * 2, k);
if(R > mid) update(L, R, mid + 1, r, rt * 2 + 1, k);
tr[rt] = tr[rt * 2] + tr[rt * 2 + 1];
}
long long query(int L, int R, int l, int r, int rt)
{
if(L <= l && r <= R)
return tr[rt];
pushdown(rt, r - l + 1);
long long res = 0;
int mid = (l + r) >> 1;
if(L <= mid) res += query(L, R, l, mid, rt * 2);
if(R > mid) res += query(L, R, mid + 1, r, rt * 2 + 1);
return res;
}
long long qq(int x, int y)
{
long long ans = 0;
while(top[x] != top[y])
{
// if(dep[top[x]] < dep[top[y]]) swap(x, y);
ans += query(id[top[x]], id[x], 1, n, 1);
x = fa[top[x]];
}
if(dep[x] > dep[y]) swap(x, y);
ans += query(id[x], id[y], 1, n, 1);
return ans;
}
signed main()
{
cin >> n >> m;
for(int i = 1;i <= n;i ++) cin >> w[i];
for(int i = 1;i < n;i ++)
{
int u, v;
cin >> u >> v;
add(u, v), add(v, u);
}
dfs1(1, 0);
dfs2(1, 1);
build(1, n, 1);
while(m --)
{
int op, x, k;
cin >> op >> x;
if(op != 3) cin >> k;
if(op == 1)
update(id[x], id[x], 1, n, 1, k);
if(op == 2)
update(id[x], id[x] + size[x] - 1, 1, n, 1, k);
else
if (op == 3) cout << qq(x, 1) << endl;
}
return 0;
}
```
by Genshineer @ 2023-09-23 16:14:57
@[long_long_integer](/user/191248) 这个要特判是题目的问题吗，谢谢大佬了，这道板子卡了我三天呜呜呜
by xiaozhuo @ 2023-09-24 13:35:52
@[xiaozhuo](/user/355377) 应该是写法的问题，这么写就是容易挂（
by Genshineer @ 2023-09-24 13:50:37