问题描述:
一棵树有 n 个点，n – 1 条无向边，边长都为 1，第 i 个点的权值为 valuei 。做 m 次操作，操作有以下两种：
0 k k 与点 x 距离不超过 k 的点，输出所有这些点的价值之和；
1 x y 修改valuex = y。
为了体现程序的在线性，操作中的x、 y、k都需要异或程序上一次的输出进行解密，如果之前没有输出，则默认上一次的输出为0。≤
| 输入：第 1 行输入整数 n 和 m。第 2 行输入 n 个正整数，其中第 i 个数表示valuei 。后面 n – 1行中，每行输入两个正整数 u 和 v ，表示 u 和 v 之间有一条无向边。后面 m 行中，每行输入3个数，表示m 次操作。 |
| 输出：对每个查询，输出一行，包含一个正整数。 |
| 数据范围：1 ≤ n，m ≤ 105 |
| 输入样例 | 输出样例 |
| 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 | 11100101 |
动态点分治
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#define maxn 100005
using namespace std;
typedef long long ll;
int read() { //读取输入 数值
int x = 0, f = 1, ch = getchar();
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();} // 负数
while(isdigit(ch))
x = (x << 1) + (x << 3) + ch - '0', ch = getchar(); // 新数字 = 旧数字 * 10 + 读取新数字
return x * f;
}
struct edge {int to, nxt;} e[maxn << 1];
int head[maxn], k = 0;
void add(int u, int v) {e[k] = {v, head[u]}; head[u] = k++;} //加边
int n, m, a[maxn];
int dep[maxn], st[maxn << 1][20], num[maxn], tot = 0; //深度、公共祖先的st表、这个数第一次出现的位置、记录遍历序号
int get_min(int a, int b){ //返回深度更小的节点
return dep[a] < dep[b]? a : b;
}
void dfs(int u, int fa) { //欧拉序
st[++tot][0] = u; num[u] = tot;
for(int i = head[u], v; ~i; i = e[i].nxt) { //遍历树
v = e[i].to; if(v == fa) continue; //剪枝：父节点
dep[v] = dep[u] + 1; dfs(v, u); st[++tot][0] = u; //深渡+1，dfs递归，记录递归节点顺序
}
}
int root, size[maxn], part[maxn], max_part, all_part = 0; //重心点、包含自己的子节点总和，去掉重心时最大的连通块、递归时的最大树、整个子树大小
bool vis[maxn];
void get_root(int u, int fa) {
size[u] = 1; part[u] = 0; all_part++;
for(int i = head[u], v; ~i; i = e[i].nxt) {
v = e[i].to; if(v == fa || vis[v]) continue;
get_root(v, u); size[u] += size[v]; //递归回来将子节点的大小添加到父节点
part[u] = max(part[u], size[v]); //与子树比较
}
part[u] = max(part[u], max_part - size[u]); //加上父节点以上的比较
if(part[u] < part[root]) root = u; //更新重心
}
int sz[maxn], fa[maxn]; //子节点数量+1，父节点
vector<int> t[maxn][2]; //0：子节点的st表.1：向父节点上更新时，删除掉子节点与父结点重复的部分
void slv(int u) {
vis[u] = true; sz[u] = all_part + 1; //all_part是求重心的时候算的整个子树大小，但是要+1才行
t[u][0].resize(sz[u] + 1); t[u][1].resize(sz[u] + 1); //这里+1是因为算上0位置
for(int i = head[u], v; ~i; i = e[i].nxt) { //遍历树
v = e[i].to; if(vis[v]) continue; //遍历过的节点跳过
max_part = size[v]; //只递归子树的子节点
all_part = root = 0; //初始化
get_root(v, u); //寻找子树的重心
fa[root] = u; slv(root);
}
}
int get_dis(int u, int v) { //返回两点间的最近距离
register int x = num[u], y = num[v]; if(x > y) swap(x, y); //按照欧拉序排xy的前后顺序
register int len = (int)log2(y - x + 1), lca = get_min(st[x][len], st[y - (1 << len) + 1][len]); //用log2求出两节间点长度，用st表找到公共祖先
return dep[u] + dep[v] - (dep[lca] << 1); //左节点深度 + 右节点深度 - 公共祖先节点的深度
}
//两行树状数组
void ist(int u, int op, int x, int w) { //修改st表
x++;
for(; x <= sz[u]; x += (x & -x))
t[u][op][x] += w;
}
int ask(int u, int op, int x) { //查询st表
x++;
int res = 0;
for(x = min(x, sz[u]); x; x -= (x & -x)) //树状数组：如果x是以2为底的指数，运行一次就结束，如果不是会一点一点减到二进制再一次结束
res += t[u][op][x]; return res;
}
void update(int u, int val) { //楼上树状数组，求答案的时候一定记得上界取min
for(int i = u; i; i = fa[i])
ist(i, 0, get_dis(u, i), val);
for(int i = u; fa[i]; i = fa[i])
ist(i, 1, get_dis(u, fa[i]), val);
}
signed main() {
n = read(), m = read(); memset(head, -1, sizeof head); //节点数量，询问次数，初始化
for(int i = 1; i <= n; i++) a[i] = read(); //读取节点
for(int i = 1, u, v; i < n; i++) u = read(), v = read(), add(u, v), add(v, u); //建树
root = 0, max_part = part[0] = n; get_root(1, 0);
dfs(root, 0);
slv(root); //建点分树
dep[0] = n + n;
for(int i = 1; (1 << i) <= tot; i++)
for(int j = 1; j + (1 << i) <= tot; j++)
st[j][i] = get_min(st[j][i - 1], st[j + (1 << (i - 1))][i - 1]); //求LCA，st表：i 结点往上的第 2^k 个节点（包括i节点）
for(int i = 1; i <= n; i++)
update(i, a[i]); //更新值
int ans = 0;
while(m--) {
register int op = read(), x = read(), y = read();
x ^= ans, y ^= ans;
if(!op) {
ans = ask(x, 0, y); //获取子树的范围内的节点值
for(int i = x; fa[i]; i = fa[i]) { //逐级遍历父节点，加上父结点的范围节点
register int d = get_dis(x, fa[i]); //往上跳。因为点分树距离不单调所以都要求
if(y >= d) //超过范围停止
ans += ask(fa[i], 0, y - d) - ask(i, 1, y - d); //for循环累计（父节点范围 - 重复的节点）
}
printf("%d\n", ans);
} else update(x, y - a[x]), a[x] = y; //更新st表，更改节点值
}
return 0;
}
笔记：动态分治需要建立分点树，分点树是一个虚树，将每一个连通块的重心逐级连接起来，将同层的重心连接起来的点分树深度最小。st表是用动态规划的方式做的预处理，可以大大减少时间的复杂度，修改节点数据时，只修改st表上于该节点相关的区间结果即可。
版权声明：
本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。本文链接：https://blog.csdn.net/qq_43326267/article/details/114901469