【9】点分治 & 点分树学习笔记
Eason_cyx
·
·
算法·理论
点分治
引入
P3806 【模板】点分治
给定一棵有 n 个点的带权树，m 次询问，每次给定 k，查询是否存在树上两点路径长度为 k。
----
这题乍一看只能 $O(n^2 m\log n)$ 的暴力，显然无法通过。
下面我们引入一种树上的分治做法，可以在 $O(nm \log n)$ 时间内解决这个问题。
## 算法流程
首先我们在整棵树上找到树的重心作为新的根，那么此时树上的所有路径就被分为两类：
- 经过根的
- 不经过根的
我们依次来考虑。
### 1. 经过根的路径
我们可以一个一个子树地考虑，每次我们 DFS 将所有点到根的距离处理出来，假设某个点到根的距离为 $x$，那么我们只需要查询前面已经处理过的子树中有无点到根的距离为 $k-x$ 即可，因为这题最大的 $k$ 只到 $10^7$，直接开一个 `bool` 数组记录即可。
### 2. 不经过根的路径
此时我们不好处理，怎么办呢？我们可以将根这个点去掉，此时整棵树就拆分成了若干棵小树，我们再重复刚才的过程递归下去即可。
该做法的正确性显然，那么时间复杂度呢？每一次在一棵树中进行的操作都是 $O(nm)$ 的，而根据重心性质每次树的大小至少减少一半，因此这个递归应当会进行 $O(\log n)$ 轮，所以总时间复杂度也就是 $O(nm \log n)$。
### 代码
代码细节还是很多的，尤其需要注意的是所有已经考虑过的重心都需要做上标记，后续无论如何不可以再访问。
:::info[Code]{open}
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5; bool has[10000005];
int k[N], tot, siz[N], cent, dep[N], m, ans[N], vis[N];
vector<pair<int, int>> e[N]; vector<int> a, b;
void find_ct(int now, int fa) {
siz[now] = 1; int mx = 0;
for(auto [x, y] : e[now])
if(x == fa || vis[x]) continue;
else find_ct(x, now),
mx = max(mx, siz[x]),
siz[now] += siz[x];
mx = max(mx, tot - siz[now]);
if(mx <= (tot / 2)) cent = now;
} void dfs(int now, int rt, int w) {
dep[now] = dep[rt] + w;
a.push_back(dep[now]);
b.push_back(dep[now]);
for(auto [x, y] : e[now])
if(x == rt || vis[x]) continue;
else dfs(x, now, y);
} void solve(int now) {
if(tot == 1) return ; dep[now] = 0;
vis[now] = 1; b.clear();
for(auto [x, y] : e[now]) {
if(vis[x]) continue;
a.clear();
dfs(x, now, y);
for(auto x : a)
for(int i = 1;i <= m;i++)
if(x <= k[i] && has[k[i] - x])
ans[i] = 1;
for(auto x : a) if(x <= 10000000) has[x] = 1;
for(int i = 1;i <= m;i++)
if(has[k[i]]) ans[i] = 1;
} for(auto x : b) if(x <= 10000000) has[x] = 0;
for(auto [x, y] : e[now]) {
if(vis[x]) continue;
tot = siz[x]; find_ct(x, now);
solve(cent);
}
} int main() {
int n; cin >> n >> m;
for(int i = 1, u, v, w;i < n;i++)
cin >> u >> v >> w,
e[u].push_back({v, w}),
e[v].push_back({u, w});
for(int i = 1;i <= m;i++) cin >> k[i];
tot = n; find_ct(1, 0); solve(cent);
for(int i = 1;i <= m;i++)
cout << (ans[i] ? "AYE" : "NAY") << endl;
return 0;
}
```
:::
## 例题
### [P2634 [国家集训队] 聪聪可可](https://www.luogu.com.cn/problem/P2634)
首先，这题从模板的存在性变成了计数，怎么办呢？很简单，我们只需要将 `has` 数组从 `bool` 改成 `int`，每次从赋值改为增加即可。
其次，如果我们直接累加边权，那么子树之间统计的时候就需要枚举值域内所有 $3$ 的倍数，稳稳 TLE。那怎么办呢？很简单，我们将所有的边权，深度等信息全部对 $3$ 取模，这样统计时就只有 $0,1,2$ 这三种情况啦。
剩下的就是板子。
:::info[Code]
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 3e4 + 5; int has[3];
int k[N], tot, siz[N], cent, dep[N], m, vis[N], sum;
vector<pair<int, int>> e[N]; vector<int> a, b;
void find_ct(int now, int fa) {
siz[now] = 1; int mx = 0;
for(auto [x, y] : e[now])
if(x == fa || vis[x]) continue;
else find_ct(x, now),
mx = max(mx, siz[x]),
siz[now] += siz[x];
mx = max(mx, tot - siz[now]);
if(mx <= (tot / 2)) cent = now;
} void dfs(int now, int rt, int w) {
dep[now] = (dep[rt] + w) % 3;
siz[now] = 1;
a.push_back(dep[now]);
b.push_back(dep[now]);
for(auto [x, y] : e[now])
if(x == rt || vis[x]) continue;
else dfs(x, now, y), siz[now] += siz[x];
} void solve(int now) {
dep[now] = 0;
vis[now] = 1; b.clear();
for(auto [x, y] : e[now]) {
if(vis[x]) continue;
a.clear();
dfs(x, now, y);
for(auto x : a)
sum += has[(x == 0 ? 0 : 3 - x)];
for(auto x : a) has[x]++, sum += !x;
} has[0] = has[1] = has[2] = 0;
for(auto [x, y] : e[now])
dfs(x, now, y);
for(auto [x, y] : e[now]) {
if(vis[x]) continue;
tot = siz[x]; a.clear(); find_ct(x, now);
solve(cent);
}
} int main() {
int n; cin >> n;
for(int i = 1, u, v, w;i < n;i++)
cin >> u >> v >> w, w %= 3,
e[u].push_back({v, w}),
e[v].push_back({u, w});
tot = n; find_ct(1, 0); solve(cent);
sum = sum * 2 + n; int ss = n * n;
int p = __gcd(sum, ss);
cout << sum / p << "/" << ss / p << endl;
return 0;
}
```
:::
### [P4149 [IOI 2011] Race](https://www.luogu.com.cn/problem/P4149)
因为 $k \le 10^6$，所以我们直接开一个数组 $mn_i$ 记录当长度为 $i$ 时的最少边数。剩下的就是板子啦~
时间复杂度 $O(n \log n)$。
:::info[Code]
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, k; vector<pair<int, int>> e[N]; stack<int> S, T, R;
int siz[N], cent, tot, _siz[N], dep[N], dis[N], mn[N], ans, mn2[N]; bool vis[N];
void find_ct(int now, int fa) {
_siz[now] = 1; int mx = 0;
for(auto [x, y] : e[now])
if(vis[x] || x == fa) continue;
else find_ct(x, now),
mx = max(mx, _siz[x]),
_siz[now] += _siz[x];
mx = max(mx, tot - _siz[now]);
if(mx <= (tot / 2)) cent = now;
} void dfs(int now, int fa, int w) {
siz[now] = 1;
dep[now] = dep[fa] + w; dis[now] = dis[fa] + 1;
if(dep[now] <= k)
mn[dep[now]] = min(mn[dep[now]], dis[now]),
S.push(dep[now]), R.push(dep[now]);
for(auto [x, y] : e[now])
if(vis[x] || x == fa) continue;
else dfs(x, now, y), siz[now] += siz[x];
} void solve(int now) {
vis[now] = 1; dep[now] = dis[now] = 0; mn[0] = 0;
for(auto [x, y] : e[now]) {
if(vis[x]) continue; dfs(x, now, y);
while(!S.empty()) {
if(mn[S.top()] == n) continue;
if(mn2[k - S.top()] < n)
ans = min(ans, mn[S.top()] + mn2[k - S.top()]);
T.push(S.top()); S.pop();
} while(!T.empty()) {
mn2[T.top()] = min(mn2[T.top()], mn[T.top()]);
mn[T.top()] = n; T.pop();
}
} while(!R.empty()) mn2[R.top()] = n, R.pop();
for(auto [x, y] : e[now]) {
if(vis[x]) continue;
tot = siz[x]; find_ct(x, now); solve(cent);
}
} int main() {
cin >> n >> k;
for(int i = 1, u, v, w;i < n;i++)
cin >> u >> v >> w, u++, v++,
e[u].push_back({v, w}),
e[v].push_back({u, w});
for(int i = 1;i <= k;i++) mn[i] = mn2[i] = n; ans = n;
tot = n; find_ct(1, 0); solve(cent);
cout << (ans == n ? -1 : ans) << endl;
return 0;
}
```
:::
### [P4178 Tree](https://www.luogu.com.cn/problem/P4178)
这题将长度正好为 $k$ 改成了小于等于 $k$，怎么办呢？考虑原来的过程，我们是统计有多少个等于 $k-x$ 的，现在我们改成小于等于 $k-x$ 的，自然的想到用树状数组即可。这样时间复杂度多一个 $\log$，也可以通过。
注意，清空的时候也要记得从树状数组中清空！
:::info[Code]
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 4e4 + 5; bool has[10000005];
int tree[N]; int lb(int x) { return x & (-x); }
void add(int x, int d) {
while(x <= N - 5) tree[x] += d, x += lb(x);
} int query(int x) { int s = 0;
while(x) s += tree[x], x -= lb(x); return s;
} int tot, siz[N], cent, dep[N], k, ans[N], vis[N], sum;
vector<pair<int, int>> e[N]; vector<int> a, b;
void find_ct(int now, int fa) {
siz[now] = 1; int mx = 0;
for(auto [x, y] : e[now])
if(x == fa || vis[x]) continue;
else find_ct(x, now),
mx = max(mx, siz[x]),
siz[now] += siz[x];
mx = max(mx, tot - siz[now]);
if(mx <= (tot / 2)) cent = now;
} void dfs(int now, int rt, int w) {
dep[now] = dep[rt] + w;
siz[now] = 1;
a.push_back(dep[now]);
b.push_back(dep[now]);
for(auto [x, y] : e[now])
if(x == rt || vis[x]) continue;
else dfs(x, now, y), siz[now] += siz[x];
} void solve(int now) {
if(tot == 1) return ; dep[now] = 0;
vis[now] = 1; b.clear();
for(auto [x, y] : e[now]) {
if(vis[x]) continue;
a.clear();
dfs(x, now, y);
for(auto x : a)
if(x <= k) sum += query(k - x);
for(auto x : a) if(x <= k) add(x, 1), sum++;
} for(auto x : b) if(x <= k) add(x, -1);
for(auto [x, y] : e[now])
dfs(x, now, y);
for(auto [x, y] : e[now]) {
if(vis[x]) continue;
tot = siz[x]; a.clear(); find_ct(x, now);
solve(cent);
}
} int main() {
int n; cin >> n;
for(int i = 1, u, v, w;i < n;i++)
cin >> u >> v >> w,
e[u].push_back({v, w}),
e[v].push_back({u, w});
cin >> k;
tot = n; find_ct(1, 0); solve(cent);
cout << sum << endl;
return 0;
}
```
:::
### [P2664 树上游戏](https://www.luogu.com.cn/problem/P2664)
好题，做了好久。
----
这题有很多种做法，我们考虑点分治做法。
套路的，先选出重心，然后考虑处理跨过重心的路径对路径端点答案的贡献。
我们先把整颗树扫一遍，如果**有一个点的颜色是这个点到根的路径上第一次出现**，那么其他点就都应该加上这个点的子树大小。我们后面会说明如何计算这个贡献。
先来理解一下这个是什么意思。我们用样例作为例子：
现在 $2$ 是重心，也就是现在的根。当我们遍历到 $1$ 号点的时候，其颜色在 $2 \to 1$ 路径上第一次出现，这意味着其它子树内的点（在这里就是 $3$ 和 $4$）只要到达 $1$ 子树内就会获得这个颜色 $1$，所以 $3$ 和 $4$ 的答案都应该加上 $1$ 的子树大小 $2$。
我们先用一个 $c$ 数组来记录每一种颜色在上述过程中产生的总贡献。那一个点到子树外的点的这个总贡献怎么算呢？可以发现，就是 $\sum c_i$ 再减去自己所在的子树内产生的 $c_i$ 贡献。
在这个过程中也可以看出，根节点得到的贡献就是 $\sum c$。
我们还是用上面那个例子来说明，为了方便看一点，把图再贴一遍：
考虑计算 $1$ 到其他子树内的点的答案。我们先处理 $c_i$，贡献应当长这样：
- $2$ 号点，颜色为 $2$，子树大小为 $5$，所以 $c_2 \gets c_2 + 5$；
- $1$ 号点，颜色为 $1$，子树大小为 $2$，所以 $c_1 \gets c_1 + 2$；
- $3$ 号点，颜色为 $3$，子树大小为 $1$，所以 $c_3 \gets c_3 + 1$；
- $5$ 号点，颜色为 $3$，子树大小为 $1$，所以 $c_3 \gets c_3 + 1$；
处理结束后应该有 $c=[2,5,2]$。
现在我们来看 $1$ 的贡献，先把 $1$ 这个子树内的贡献减掉，于是就有 $c'=[0,5,1]$。**注意！根节点这里将整个树的大小都加上了，但是你现在只去你子树外的点，所以这里要减掉该子树的大小。**
那么最终就有 $c'=[0,3,1]$。看一下这意味着什么：
- $1$ 去其他子树中的点，有三个路径上有颜色 $2$，答案 $+3$。
- $1$ 去其他子树中的点，有一个路径上有颜色 $3$，答案 $+1$。
所以 $1$ 目前的答案为 $4$。于是就搞定了，我们继续递归……
**慢着！我们现在只处理了子树外的路径，那该点到根的路径呢？**
这个其实方法类似，对这个子树再做一次遍历，假设有一个颜色 $i$ 在到根的路径上第一次出现，那么这个子树内所有点无论去子树外的哪个点都会经过这里，就会有这种颜色对吧，所以多出的贡献就是其他子树的点的总数减去 $c_i$，用一个标记记录要加多少，到每个点更新即可。
例如，考虑 $1$ 到根的路径，颜色 $1$ 是第一次出现，所以 $1$ 到外面每个点都会有颜色 $1$，外面一共三个点，但是路径包含颜色 $1$ 的只有 $0$ 个，所以 $1$ 的答案要加上 $3-0=3$。
这样我们就完成了一次处理，向下递归即可。
时间复杂度是 $O(n \log n)$。
---
代码还是细节挺多的，主要是需要注意处理好根，比较特殊，以及精细清空。
:::info[Code]{open}
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5; vector<int> can; stack<int> S;
int c[N], siz[N], _siz[N], tot, cent, col[N], sum, add, has[N], ans[N], ss, mx, n; bool vis[N];
vector<int> e[N];
void find_ct(int now, int fa) {
_siz[now] = 1; int mx = 0;
for(auto x : e[now])
if(x == fa || vis[x]) continue;
else find_ct(x, now),
mx = max(mx, _siz[x]),
_siz[now] += _siz[x];
mx = max(mx, tot - _siz[now]);
if(mx <= (tot / 2)) cent = now;
} void getsiz(int now, int fa) {
siz[now] = 1;
for(auto x : e[now])
if(x == fa || vis[x]) continue;
else getsiz(x, now), siz[now] += siz[x];
} void dfs(int now, int fa, bool Ty) {
has[c[now]]++; S.push(c[now]);
if(has[c[now]] == 1) {
if(!(Ty && c[now] == c[cent])) col[c[now]] += siz[now], ss += siz[now];
} for(auto x : e[now])
if(x == fa || vis[x]) continue;
else dfs(x, now, Ty);
has[c[now]]--;
} void adfs(int now, int fa) {
has[c[now]]++;
if(has[c[now]] == 1 && c[now] != c[cent])
col[c[now]] -= siz[now], ss -= siz[now];
for(auto x : e[now])
if(x == fa || vis[x]) continue;
else adfs(x, now);
has[c[now]]--;
} void proc(int now, int fa) {
has[c[now]]++; bool f = 0;
if(has[c[now]] == 1)
f = 1, add += tot - col[c[now]];
ans[now] += ss + add;
for(auto x : e[now])
if(x == fa || vis[x]) continue;
else proc(x, now);
has[c[now]]--;
if(f) add -= tot - col[c[now]];
} void solve(int now) { ss = 0;
vis[now] = 1; getsiz(now, 0); dfs(now, 0, 0);
ans[now] += ss;
for(auto x : e[now]) {
if(vis[x]) continue;
adfs(x, now); add = 0; tot -= siz[x];
col[c[now]] -= siz[x]; ss -= siz[x];
proc(x, now); col[c[now]] += siz[x];
dfs(x, now, 1); tot += siz[x]; ss += siz[x];
} while(!S.empty()) col[S.top()] = 0, S.pop();
for(auto x : e[now]) {
if(vis[x]) continue;
tot = siz[x]; find_ct(x, now);
solve(cent);
}
} signed main() {
cin >> n;
for(int i = 1;i <= n;i++)
cin >> c[i], mx = max(mx, c[i]);
for(int i = 1, u, v;i < n;i++)
cin >> u >> v,
e[u].push_back(v), e[v].push_back(u);
tot = n; find_ct(1, 0); solve(cent);
for(int i = 1;i <= n;i++) cout << ans[i] << endl;
return 0;
}
```
:::
# 点分树
## 引入
### [P6329 【模板】点分树 / 震波](https://www.luogu.com.cn/problem/P6329)
给定一棵树，$q$ 次操作，每次更改一个点的点权或查询离某个点距离不超过一个值的点的点权之和。**强制在线。**
$n,q \le 10^5$。
----
## 算法流程
点分树，又叫动态点分治，可以用来解决一类和树的形态无关的动态问题。
先来想一个问题：如果这题没有修改，还可以离线，怎么做？这个就可以用点分治解决了：将所有询问挂到询问对应的点下面，然后我们进行点分治，在枚举到这个点的时候算一下别的子树里的点对这个点的询问的答案产生的贡献即可。
现在有了修改，还强制在线，怎么做呢？下面我们来引入**点分树**这个东西：
### 建树
在点分治时，我们用很多轮选出了很多重心，现在我们把**每一轮的重心和其对应的上一轮的重心连起来。**
例如一棵树，长这样：
我们记录一下每次是哪些点作为重心：
- 第一轮，重心是 $3$。
- 第二轮，重心是 $2$ 和 $7$。
- 第三轮，重心是 $4,1,6,9$。
- 第四轮，重心是 $5,8,10$。
于是我们按照上面的方法建树：
建出来的这棵树就叫**点分树**。一般来说，我们可以在点分树上每个点建立一个数据结构来维护一些信息。下面我们来看为什么可以这样做。
可以发现，这个树和原树非常不像。那么这个树有什么性质呢？这里列举几条重要的：
- **树高为 $O(\log n)$**。不难看出树高就是递归层数，因此是 $\log n$ 级别的。
- 一个点在点分树上的子树中的点，就是其在点分治过程中作为重心时，其连通块中的点。可以根据定义来理解。
- **在点分树中，$\sum siz_i=O(n \log n)$**。因为每一层的结点都是上一层的点删去之后得到的剩下的点中的重心，那么这一层的子树大小之和应当就是 $O(n)$。而这个树只有 $O(\log n)$ 层，所以结论成立。
- 点分树上任意 $x,y$ 两点的 $\operatorname{LCA}$ 在原树中一定在 $x \to y$ 的路径上。**设 $\operatorname{LCA}$ 为 $z$，则可以转化为 $\operatorname{dis}(x,y)=\operatorname{dis}(x,z)+\operatorname{dis}(z,y)$**。
- 如何证明？
- 首先判特殊情况，如果 $x$ 在点分树上是 $y$ 的祖先或反过来，那么可以得到 $x$ 和 $y$ 在原树中一定是一个点在另一个点的子树中，这个式子显然成立，因此这种情况后面不予考虑。
- 剩下的情况，因为 $z$ 在点分树上是 $x,y$ 的祖先，所以这意味着 $z$ 在点分治过程中作为重心时，$x$ 和 $y$ 一定为它的后代。那么，我们只需要证明 $x$ 和 $y$ 不在一个大子树（即，以 $z$ 的某个儿子为根的子树）中即可。
- 这个也很好证。考虑反证，如果 $x$ 和 $y$ 在一个大子树中，那么将 $z$ 删去之后 $x$ 和 $y$ 仍在一个连通块中，我们取新的重心，会发现这个新的点在点分树上也是 $x$ 和 $y$ 的公共祖先，且深度比 $z$ 大，因此 $z$ 不是 $x$ 和 $y$ 的最近公共祖先。证毕！
- **注意：点分树上的相邻的点之间也没有任何关系，距离也不为 $1$。**
看完了性质，现在我们来看点分树怎么用。
### 处理
回到刚才那道题，我们每次需要求的是：
$$\sum_{\operatorname{dis}(x,y) \le k}a_y$$
看到这个想到什么？刚才的性质！$\operatorname{dis}(x,y)$ 可以拆成 $\operatorname{dis}(x,z)+\operatorname{dis}(z,y)$。于是，我们可以先建出点分树，然后询问给出 $x$ 之后，我们可以在点分树上枚举 $x$ 的祖先 $z$（根据性质，这样的 $z$ 只会有 $O(\log n)$ 个），然后考虑计算
$$\sum_{\operatorname{dis}(x,z)+\operatorname{dis}(z,y)\le k,z=\operatorname{LCA}(x,y)}a_y$$
一旦得到了这个，我们将所有 $z$ 的答案累加起来即可。
由于 $\operatorname{dis}(x,z)$ 是定值，下面我们将其记作 $w$。于是可以得到：
$$\operatorname{dis}(z,y)\le k-w$$
又由于更新是单点改点权，感觉上来说我们需要一个可以维护一个点，和距离和点权之和之类的有关的信息的数据结构。
于是可以想到**线段树**。（我也不知道咋想到的，好神奇）
我们在每个点 $u$ 开一个**动态开点线段树**，其中下标 $i$ 用来记录 $u$ 的子树内所有满足 $\operatorname{dis}(u,v) = i$ 的点 $v$ 的点权之和。
那么更新也容易了，就是枚举 $u$ 的所有祖先 $v$，然后在 $v$ 的线段树中 $\operatorname{dis}(u,v)$ 这个位置加上 $a_u$。（**注意！这里是原树上的距离！**）
欸等下，查询咋算啊？直接在 $z$ 的线段树上面查吗？不，因为我们要求 $\operatorname{LCA}(x,y)=z$，所以 $x$ 和 $y$ 不能在一个大子树里。那查完 $z$ 之后，不就多出来了一些 $x$ 所在大子树里面的点吗？
这个其实很好解决，设 $x$ 所在的大子树的根是 $s$，那么我们实际上需要减掉的是 $s$ 子树内与 $z$ 的距离不超过 $k-w$ 的点的个数。**但是，因为这是点分树，所以和 $s$ 距离不超过 $k-w-1$ 的点并不能推出和 $v$ 距离不超过 $k-w$**。那咋办？我们对每个点多开一个线段树，用于记录其子树内到父亲的距离为 $i$ 的点的点权和即可。
这样我们就搞定了这道题！分析一下复杂度：
空间上瓶颈是线段树，由于我们使用了动态开点，所以应当最多占用的空间就是 $\sum siz_i$，也就是 $O(n \log n)$ 级别。
时间上，瓶颈是更新 / 查询，每次会跳到 $O(\log n)$ 个结点，每个结点要花费 $O(\log n)$ 来更新 / 查询，所以总复杂度是 $O((n+q)\log^2n)$，可以通过。
注意数组别开太大，还有如果被卡常考虑倍增 LCA 换成树剖，会快很多很多。
:::info[Code]{open}
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m, val[N], _v[N], siz[N], cent, tot, fa[N], _fa[N];
int son[N], top[N], dep[N];
vector<int> e[N]; bool vis[N];
struct segtree {
struct node { int l, r, w; }; vector<node> tree;
void build() { tree.push_back({0, 0, 0}); }
int get() {
tree.push_back({0, 0, 0});
return tree.size() - 1;
} void pushup(int x) {
int sum = 0;
if(tree[x].l != 0) sum += tree[tree[x].l].w;
if(tree[x].r != 0) sum += tree[tree[x].r].w;
tree[x].w = sum;
} void update(int x, int l, int r, int y, int d) {
if(l == r) return tree[x].w += d, void();
int mid = (l + r) >> 1, cur = 0;
if(y <= mid) {
if(tree[x].l == 0) cur = get(), tree[x].l = cur;
update(tree[x].l, l, mid, y, d);
} else {
if(tree[x].r == 0) cur = get(), tree[x].r = cur;
update(tree[x].r, mid+1, r, y, d);
} pushup(x);
} int query(int x, int l, int r, int L, int R) {
if(L <= l && r <= R) return tree[x].w;
int mid = (l + r) >> 1, sum = 0;
if(L <= mid && tree[x].l)
sum += query(tree[x].l, l, mid, L, R);
if(R > mid && tree[x].r)
sum += query(tree[x].r, mid+1, r, L, R);
return sum;
}
} tr[2 * N];
void find_ct(int now, int fa) {
siz[now] = 1; int mx = 0;
for(auto x : e[now])
if(vis[x] || x == fa) continue;
else find_ct(x, now),
siz[now] += siz[x],
mx = max(mx, siz[x]);
mx = max(mx, tot - siz[now]);
if(mx <= (tot / 2)) cent = now;
} void csiz(int now, int fa) {
siz[now] = 1;
for(auto x : e[now])
if(vis[x] || x == fa) continue;
else csiz(x, now),
siz[now] += siz[x];
} void solve(int now, int pre) {
vis[now] = 1; fa[now] = pre; csiz(now, pre);
for(auto x : e[now])
if(vis[x]) continue;
else tot = siz[x],
find_ct(x, now),
solve(cent, now);
} void dfs(int now, int fa_) {
siz[now] = 1; dep[now] = dep[fa_] + 1;
int mx = 0; _fa[now] = fa_;
for(auto x : e[now]) {
if(x == fa_) continue;
dfs(x, now); siz[now] += siz[x];
if(siz[x] > mx)
mx = siz[x], son[now] = x;
}
} void proc(int now, int fa_, int rt) {
top[now] = rt;
if(son[now]) proc(son[now], now, rt);
for(auto x : e[now])
if(x == fa_ || x == son[now]) continue;
else proc(x, now, x);
} int len(int u, int v) {
int _u = u, _v = v;
while(top[_u] != top[_v]) {
if(dep[top[_u]] < dep[top[_v]])
swap(_u, _v);
_u = _fa[top[_u]];
} if(dep[_u] > dep[_v]) swap(_u, _v);
return dep[u] + dep[v] - 2 * dep[_u];
} void upd(int x, int d) {
int add = d - val[x], y = x, lst = 0; val[x] = d; while(y) {
tr[y].update(0, 0, n, len(x, y), add);
if(lst) tr[lst + n].update(0, 0, n, len(x, y), add);
lst = y; y = fa[y];
}
} int qry(int x, int k) {
int y = fa[x], lst = x, ans = tr[x].query(0, 0, n, 0, k);
while(y) {
if(len(x, y) <= k)
ans += tr[y].query(0, 0, n, 0, k - len(x, y)),
ans -= tr[lst + n].query(0, 0, n, 0, k - len(x, y));
lst = y; y = fa[y];
} return ans;
} int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> m;
for(int i = 1;i <= n;i++) cin >> _v[i];
for(int i = 1, u, v;i < n;i++)
cin >> u >> v,
e[u].push_back(v),
e[v].push_back(u);
tot = n; find_ct(1, 0); solve(cent, 0);
dfs(1, 0); proc(1, 0, 1);
for(int i = 1;i <= 2 * n;i++) tr[i].build();
for(int i = 1;i <= n;i++) upd(i, _v[i]);
int out = 0;
while(m--) {
int opt, x, y; cin >> opt >> x >> y;
x ^= out; y ^= out; if(opt == 0) y = min(y, n);
if(opt == 1) upd(x, y);
else cout << (out = qry(x, y)) << "\n";
}
return 0;
}
```
:::
# 总结 & 后记
点分治是一种很常用（？的算法，用于解决一类路径可以拆分的问题。点分树在点分治基础上，与数据结构进行了结合，来解决更困难的问题。
点分树习题好难啊 qwq，我还在学，完成之后大概会更新？awa
码字不易，能否给个赞 /wq ><
若对文章有任何问题和建议可以与作者私信交流。