树剖？
by Rem_CandleFire @ 2024-04-23 21:03:29
@[ChenZQ](/user/745358) 一眼树剖秒了
by Lian_lele @ 2024-04-23 21:05:39
```cpp
/*********************************************************************
Programname: 517.cpp
Copyright: fu**wei
Author: RF_RT & Eric unknown RFT
Date: 2024-02-01 14:06
Illustrate: RF_RT konjac's code
*********************************************************************/
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define HORIZONTAL 0, 0, 1, -1
#define VERTICAL 1, -1, 0, 0
#define SPOS string::npos
#define IOS ios::sync_with_stdio(false); \
cin.tie(0)
using namespace std;
template <class T>
inline void Read(T &Ret) {
int x = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') {
f = -1;
}
c = getchar();
}
while (isdigit(c)) {
x = (x << 1) + (x << 3) + (c ^ 48);
c = getchar();
}
Ret = x * f;
}
inline void Testcase(int &Case) {
printf("Case %d: ", ++Case);
}
typedef long long LL;
const int INF = 0x3f3f3f3f;
const LL MOD = 998244353;
const int N = 2e5 + 2;
const int M = 2e2 + 5;
const double EPS = 1e-8;
const double PI = acos(-1.0);
int T = 1, Ca;
int Head[N], Nxt[N], To[N], Num[N], n, HNT, a[N], Id[2][N], Tot, Grade[N], Op, x, y;
LL Fl[N * 4], Ans[N * 4], Tag[N * 4];
void Init() {
memset(Head, -1, sizeof(Head));
HNT = 1;
}
void Add(int u, int v) {
To[++HNT] = v;
Nxt[HNT] = Head[u];
Head[u] = HNT;
}
void Dfs(int u, int Fa) {
Tot++;
a[Tot] = Num[u], Id[0][u] = Tot, Grade[Tot] = 1;
for (int i = Head[u]; i != -1; i = Nxt[i]) if (To[i] != Fa) {
Dfs(To[i], u);
}
Tot++;
a[Tot] = -Num[u], Id[1][u] = Tot, Grade[Tot] = -1;
}
int Ls(int x) {
return x * 2;
}
int Rs(int x) {
return x * 2 + 1;
}
void Pushup(int p) {
Ans[p] = Ans[Ls(p)] + Ans[Rs(p)];
}
void Build(int p, int l, int r) {
if (l == r) {
Ans[p] = a[l];
Fl[p] = Grade[l];
return ;
}
int Mid = (l + r) >> 1;
Build(Ls(p), l, Mid);
Build(Rs(p), Mid + 1, r);
Pushup(p);
Fl[p] = Fl[Ls(p)] + Fl[Rs(p)];
}
void Pushdown(int p) {
Ans[Ls(p)] += Fl[Ls(p)] * Tag[p];
Ans[Rs(p)] += Fl[Rs(p)] * Tag[p];
Tag[Ls(p)] += Tag[p];
Tag[Rs(p)] += Tag[p];
Tag[p] = 0;
}
LL Query(int p, int l, int r, int nl, int nr) {
if (l <= nl && r >= nr) {
return Ans[p];
}
if (Tag[p]) {
Pushdown(p);
}
int Mid = (nl + nr) >> 1;
LL Ret = 0;
if (Mid >= l) {
Ret += Query(Ls(p), l, r, nl, Mid);
}
if (Mid + 1 <= r) {
Ret += Query(Rs(p), l, r, Mid + 1, nr);
}
return Ret;
}
void Update(int p, int l, int r, int nl, int nr, int x) {
if (l <= nl && r >= nr) {
Ans[p] += Fl[p] * x;
Tag[p] += x;
return ;
}
if (Tag[p]) {
Pushdown(p);
}
int Mid = (nl + nr) >> 1;
if (Mid >= l) {
Update(Ls(p), l, r, nl, Mid, x);
}
if (Mid + 1 <= r) {
Update(Rs(p), l, r, Mid + 1, nr, x);
}
Pushup(p);
}
signed main(int argc, char *argv[]) {
#ifdef _WIN32
freopen("xxx.in", "r", stdin);
freopen("xxx.out", "w", stdout);
#else
#endif
Init();
scanf("%d%d", &n, &T);
for (int i = 1; i <= n; i++) {
Read(Num[i]);
}
for (int i = 2, u, v; i <= n; i++) {
Read(u);
Read(v);
Add(u, v);
Add(v, u);
}
Dfs(1, 0);
Build(1, 1, Tot);
while (T--) {
Read(Op);
Read(x);
if (Op == 3) {
printf("%lld\n", Query(1, 1, Id[0][x], 1, Tot));
} else {
Read(y);
if (Op == 1) {
Update(1, Id[0][x], Id[0][x], 1, Tot, y);
Update(1, Id[1][x], Id[1][x], 1, Tot, y);
} else {
Update(1, Id[0][x], Id[1][x], 1, Tot, y);
}
}
}
return 0;
}
```
by EricEnkAliTheFox @ 2024-04-23 21:11:31
@[ChenZQ](/user/745358)
by EricEnkAliTheFox @ 2024-04-23 21:12:11
那我还以为是线段树呢
by EricEnkAliTheFox @ 2024-04-23 21:12:30
@[ChenZQ](/user/745358) 他的名字都表明了是dfs序+线段树吧/cf
by Hoks @ 2024-04-23 21:22:40
根本不用树剖了
by Hoks @ 2024-04-23 21:22:58
@[Hoks](/user/551100) 貌似需要，操作3需要剖一下好像
by Lian_lele @ 2024-04-23 21:45:19
@[Lian_lele](/user/923248) 哦哦降智了/kel，鉴定为做了100+树剖也就那样
by Hoks @ 2024-04-23 21:47:44
@[Lian_lele](/user/923248) 不需要啊，甚至树状数组就能做。
对于每个点维护一个值：$dis_i$ 表示该点到根的距离，然后修改一个点，那么该点子树下的所有的点的权值都会 $+ a$，然后又由于一棵子树的 dfs序是连续的，那么直接树状数组维护 $dis_i$ 的差分。就可以了。
by Ice_lift @ 2024-04-24 15:41:35