题面

大秦为你打开题目传送门

题目背景

模板题，没有 $rap$ 。

题目描述

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

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

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

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

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

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

输入格式

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

第二行包含 $n$ 个正整数，第 $i$ 个数表示 $value_i$ 。

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

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

输出格式

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

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
9
10
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

1
11100101

提示

数据规模与约定

对于 $100 \%$ 的数据，有 $1\leq n,m\leq 10^5, 1\leq u,v,x\leq n, 1\leq value_i,y\leq 10^4,0\leq k\leq n-1$ 。

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

说明

题目来源：BZOJ3730。

思路

首先我们知道，单次询问，树上路径的问题可以用点分治解决。

但如果加上什么 $q$ 次询问之类的东西怎么办呢？比如说这题。

显然每次都跑一遍点分治时间复杂度肯定吃不消。

考虑把点分治的过程离线下来，将当前树的重心与上一层的树的重心连边，这样就可以得到一棵树，我们称之为“点分树”

比如说我们有如下图所示的树与基于其建立的点分树：

imgimg

那么这棵树对于我们做题有什么帮助呢？

有的问题我们不是非常关心树的形态特点，比如路径问题，联通块问题，寻找关键点问题等等，以路径问题为例，我们不一定非得查到 $p,q$ 的 LCA 才可以处理 $p,q$ 的路径信息，相反，我们可以随便从这个路径上寻找一个分割点 $t$ ，只要我们可以快速的处理 $p$ 到 $t$ 和 $q$ 到 $t$ 的信息，我们就可以处理 $p$ 到 $q$ 的信息。

而点分树恰恰就是对原树做了这样的映射。

然后处理就简单了，，，，

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <bits/stdc++.h>
#define REP(u) for(int i = H[u], v; i, v = E[i].v; i = E[i].n)
using namespace std;
const int maxn = 2e5 + 111, inf = 1e9 + 7;
int N, M, tot, ans, rt, sum, minn, cnt;
int val[maxn], H[maxn], sz[maxn], fa[maxn], dep[maxn], pos[maxn], ol[maxn<<1][21], lg[maxn<<1];
//val表示该城市的价值，sz表示该点子树的大小，fa表示该点点分树上的父亲节点，dep表示该点的深度 
bool vis[maxn];
vector<int>C[2][maxn];
//C[0][i]表示i子树内节点对i的贡献
//C[1][i]表示i子树内节点对i父亲的贡献 
struct edge {
	int n, v;
}E[maxn<<1];
void add(int u, int v)
{
	E[++tot] = (edge) {H[u], v};
	H[u] = tot;
}
void dfs0(int u, int f)
{
	ol[++cnt][0] = u, pos[u] = cnt;
	REP(u) if(v ^ f) dep[v] = dep[u] + 1, dfs0(v, u), ol[++cnt][0] = u;
}
int get_min(int a, int b)
{
	return dep[a] < dep[b] ? a : b;
}
void get_ol() 
{
	for(int i = 1; i <= cnt; ++i) lg[i] = 31 - __builtin_clz(i);
	for(int t = 1; 1 << t <= cnt; ++t)
		for(int i = 1; i + (1 <<t) <= cnt; ++i)
			ol[i][t] = get_min(ol[i][t - 1], ol[i + (1 << (t - 1))][t - 1]);
}
int get_dis(int u, int v)
{
	if(pos[u] > pos[v]) swap(u, v);
	int uu = pos[u], vv = pos[v], len = vv - uu + 1;
	int lca = get_min(ol[uu][lg[len]], ol[vv - (1 << lg[len]) + 1][lg[len]]);
	return dep[u] + dep[v] - 2 * dep[lca];
}
#define lowbit(x) (x & -x)
void upd(int u, int opt, int x, int addv)
{
	x++;
	for(int i = x; i <= sz[u]; i += lowbit(i)) C[opt][u][i] += addv;
}
int qry(int u, int opt, int x)
{
	x++;
	int res = 0;
	x = min(x, sz[u]);
	for(int i = x; i; i -= lowbit(i)) res += C[opt][u][i];
	return res;
}
void find_rt(int u, int f) //找重心 
{
	sz[u] = 1;
	int res = 0;
	REP(u) if(f ^ v && !vis[v]) find_rt(v, u), sz[u] += sz[v], res = max(res, sz[v]);
	res = max(res, sum - sz[u]);
	if(res < minn) minn = res, rt = u; 
}
void dfs(int u) //建立点分树 
{
	vis[u] = 1;
	sz[u] = sum+1;
	C[0][u].resize(sz[u]+1);
	C[1][u].resize(sz[u]+1);
	REP(u) if(!vis[v]) 
	{
		sum = sz[v], rt = 0, minn = inf;
		find_rt(v, 0);
		fa[rt] = u;
		dfs(rt);
	}
}
void modify(int u, int w)
{
	for(int i = u; i; i = fa[i]) upd(i, 0, get_dis(u, i), w); 
	for(int i = u; fa[i]; i = fa[i]) upd(i, 1, get_dis(u, fa[i]), w);	
}
int main()
{
	int opt, x, y;
	scanf("%d%d", &N, &M);
	for(int i = 1; i <= N; ++i) scanf("%d", &val[i]);
	for(int i = 1; i <  N; ++i) scanf("%d%d", &x, &y), add(x, y), add(y, x);
	dfs0(1, 0);
	get_ol();
	sum = N, minn = inf;
	find_rt(1, 0);
	dfs(rt);
	for(int i = 1; i <= N; ++i) modify(i, val[i]); 
	while(M--)
	{
		scanf("%d%d%d", &opt, &x, &y);
		x ^= ans, y ^= ans; 
		if(!opt) 
		{
			ans = 0;
			ans += qry(x, 0, y); //x子树内到其距离为y的点对x的贡献 
			for(int i = x; fa[i]; i = fa[i])
			{
				int dis = get_dis(x, fa[i]);  
				if(y >= dis) ans += qry(fa[i], 0, y - dis) - qry(i, 1, y - dis); //x子树外到其距离为y的点 
				//fa[i]子树中除x所在子树对x的贡献 即为 fa[i]子树对它的总贡献 减去 x所在子树对fa[i]的贡献 
			}
			printf("%d\n", ans);
		}
		else modify(x, y - val[x]), val[x] = y; //利用差分的办法修改其对点分树上祖先的贡献 
	}
	return 0;
}