【洛谷】P6319

【模板】点分树 | 震波

#数据结构 #树形结构 #分治

题目背景

模板题，没有 $rap$ 。

题目描述

在一片土地上有 $n$ 个城市，通过 $n-1$ 条无向边互相连接，形成一棵树的结构，相邻两个城市的距离为 $1$，其中第 $i$ 个城市的价值为 $valu{e}_i$。

不幸的是，这片土地常常发生地震，并且随着时代的发展，城市的价值也往往会发生变动。

接下来你需要在线处理 $m$ 次操作：

0 x k 表示发生了一次地震，震中城市为 $x$，影响范围为 $k$，所有与 $x$ 距离不超过 $k$ 的城市都将受到影响，该次地震造成的经济损失为所有受影响城市的价值和。

1 x y 表示第 $x$ 个城市的价值变成了 $y$ 。

为了体现程序的在线性，操作中的 $x$、$y$、$k$ 都需要异或你程序上一次的输出来解密，如果之前没有输出，则默认上一次的输出为 $0$ 。

输入格式

第一行包含两个正整数 $n$ 和 $m$ 。

第二行包含 $n$ 个正整数，第 $i$ 个数表示 $valu{e}_i$ 。

接下来 $n-1$ 行，每行包含两个正整数 $u$、$v$，表示 $u$ 和 $v$ 之间有一条无向边。

接下来 $m$ 行，每行包含三个数，表示 $m$ 次操作。

输出格式

包含若干行，对于每个询问输出一行一个正整数表示答案。

样例 #1

样例输入 #1

8 1
1 10 100 1000 10000 100000 1000000 10000000
1 2
1 3
2 4
2 5
3 6
3 7
3 8
0 3 1

样例输出 #1

11100101

提示

数据规模与约定

对于 $100\%$ 的数据，有 $1\le n,m\le 10^5,1\le u,v,x\le n,1\le valu{e}_i,y\le 10^4,0\le k\le n-1$ 。

upd：样例范围与题目真实数据范围不同，以提示中给出的数据范围为准。

说明

题目来源：BZOJ3730。

思路

点分树模板题，先建点分树（重心树），然后对每个点开两颗动态开点线段树，线段树上的区间表示距离，维护点权之和。

需要预处理出点分树上所有的祖先，修改时就暴力跳父节点，然后维护两颗线段树。查询的时候也是暴力跳父节点，然后使用容斥原理来查询答案。

由于点分树上深度最大为$lo{g}_{2}n$，因此整体时间复杂度为$O(mlo{g}_2^{2}n)$

代码

const int N = 2e5 + 10;int n, m;
int w[N];
std::vector<int>e[N];struct LCA {int dep[N], fa[N][20];void dfs(int u, int f) {dep[u] = dep[f] + 1;fa[u][0] = f;for (int i = 1; i <= 19; ++i) {fa[u][i] = fa[fa[u][i - 1]][i - 1];}for (auto& v : e[u]) {if (v == f) continue;dfs(v, u);}}int lca(int u, int v) {if (dep[u] < dep[v]) std::swap(u, v);for (int i = 19; i >= 0; --i) {if (dep[fa[u][i]] >= dep[v]) {u = fa[u][i];}}if (u == v) return u;for (int i = 19; i >= 0; --i) {if (fa[u][i] != fa[v][i]) {u = fa[u][i];v = fa[v][i];}}return fa[u][0];}int getdis(int x, int y) {return dep[x] + dep[y] - 2 * dep[lca(x, y)];}}lca;struct Seg {int tot = 0;int root[N]; //每个线段树的根节点int lc[N * 40], rc[N * 40], sum[N * 40];void push_up(int u) {sum[u] = sum[lc[u]] + sum[rc[u]];}void update(int& u, int l, int r, int x, int val) { if (!u) u = ++tot;if (l == r) {sum[u] += val;return;}int mid = l + r >> 1;if (x <= mid) update(lc[u], l, mid, x, val);else {update(rc[u], mid + 1, r, x, val);}push_up(u);}int query(int u, int l, int r, int x, int y) {if (!u || r<x || l>y) return 0;if (x <= l && y >= r) {return sum[u];}int mid = l + r >> 1;return query(lc[u], l, mid, x, y) + query(rc[u], mid + 1, r, x, y);}}seg, ch;struct PointTree { //点分树int root, sum, siz[N], mxp[N], del[N];void findwc(int u, int fa) { //找重心siz[u] = 1;mxp[u] = 0;for (auto& v : e[u]) {if (v == fa || del[v]) continue;findwc(v, u);siz[u] += siz[v];mxp[u] = std::max(mxp[u], siz[v]);}mxp[u] = std::max(mxp[u], sum - siz[u]);if (mxp[u] < mxp[root]) {root = u;}}void getroot(int x, int size) { //找出根root = 0;mxp[root] = sum = size;findwc(x, -1);findwc(root, -1);}int dis[N][20], dep[N], fa[N];void build_sg(int u, int fa, int wc, int d) {seg.update(seg.root[wc], 0, n, d, w[u]);for (auto& v : e[u]) {if (v == fa || del[v]) continue;build_sg(v, u, wc, d + 1);}}void build_ch(int u, int fa, int wc, int d) {ch.update(ch.root[wc], 0, n, d, w[u]);for (auto& v : e[u]) {if (v == fa || del[v]) continue;build_ch(v, u, wc, d + 1);}}void build(int x) { //建点分树del[x] = true;build_sg(x, -1, x, 0);for (auto& v : e[x]) {if (del[v])continue;getroot(v, siz[v]);build_ch(v, -1, root, 1);fa[root] = x; dep[root] = dep[x] + 1;build(root);}}void init() {getroot(1, n);build(root);lca.dfs(1, -1);for (int i = 1; i <= n; ++i) {for (int j = i; j; j = fa[j]) {dis[i][dep[i] - dep[j]] = lca.getdis(i, j);}}}int query(int x, int y) {int res = seg.query(seg.root[x], 0, n, 0, y);for (int i = x; fa[i]; i = fa[i]) {int d = dis[x][dep[x] - dep[fa[i]]];res += seg.query(seg.root[fa[i]], 0, n, 0, y - d);res -= ch.query(ch.root[i], 0, n, 0, y - d);}return res;}void update(int x, int y) {seg.update(seg.root[x], 0, n, 0, y - w[x]);for (int i = x; fa[i]; i = fa[i]) {int d = dis[x][dep[x] - dep[fa[i]]];seg.update(seg.root[fa[i]], 0, n, d, y - w[x]);ch.update(ch.root[i], 0, n, d, y - w[x]);}} 
} pt;
void solve() {std::cin >> n >> m;for (int i = 1; i <= n; ++i) {std::cin >> w[i];}for (int i = 1; i <= n - 1; ++i) {int u, v;std::cin >> u >> v;e[u].emplace_back(v);e[v].emplace_back(u);}pt.init();int last = 0;while (m--) {int op, x, y;std::cin >> op >> x >> y;x ^= last, y ^= last;if (op == 1) { //修改pt.update(x, y);w[x] = y;}else { //查询last = pt.query(x, y);std::cout << last << "\n";}}
}signed main() {std::ios::sync_with_stdio(0);std::cin.tie(0);std::cout.tie(0);int t = 1;//std::cin >> t;while (t--) {solve();}return 0;
}