点分治、动态点分治
前言
为什么窝点分治切的比FFT还慢T^T（虽说FFT已经忘的一干二净了_(:з)∠)_）
洛谷是个好地方，这群OIer真是niubility！
说回来点分治，分治意味着高效，点分治是一种高效的处理树上路径问题的工具（递归套递归套递归…）
点分治题目最难的可能就是，要猜出他是一道点分治题目了吧QAQ
蒟蒻表示切不动
边码边发现好像从未写过这么长的题解 QAQ
洛谷 P3806 - 【模板】点分治1
链接
https://www.luogu.org/problemnew/show/P3806
思路
考虑当前以rt为根的子树，树上距离为k的点对，有两种情况
要么他们经过rt，要么经过rt的子树的根
对于第二种情况，可以递归解决，因此只考虑如何求出第一种情况的点对数量
第一种情况的点对，满足lca(u, v) = rt && d[u] + d[v] == k，此处难以解决的是lca(u, v) = rt，那么就倒过来考虑，考虑求cnt(d[u] + d[v] == k) - cnt(d[u] + d[v] == k && lca(u, v) != rt)，那么只需要DFS一遍算出d数组，排序一遍，再用O(n)的方法算出cnt(d[u] + d[v] == k)，再容斥一下即可算出第一种情况的点对数量，然后再递归处理第二种情况即可
但是直接递归的话，若树退化就GG，每次要排序和用O(n)方法处理的n非常大，可以用树形DP中的求树的重心算出点分树的重心，每次递归处理子树重心，这样每次递归处理的n就得到了控制
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 10000 + 15;
typedef long long ll;
const int inf = 0x3f3f3f3f;
struct edge{
int v, w, nxt;
};
int head[N], tot;
bool used[N];
edge e[N << 1];
int sum[N], maxsum[N], d[N], pd;
inline void init(){
tot = 0;
memset(head, -1, sizeof(head));
}
inline void addEdge(int u, int v, int w){
e[tot] = edge{v, w, head[u]};
head[u] = tot++;
}
void getRoot(int u, int pre, int size, int& rt){
sum[u] = 1, maxsum[u] = 0;
for(int i = head[u]; ~i; i = e[i].nxt){
int v = e[i].v;
if(used[v] || v == pre) continue;
getRoot(v, u, size, rt);
sum[u] += sum[v];
maxsum[u] = max(maxsum[u], sum[v]);
}
maxsum[u] = max(maxsum[u], size - sum[u]);
if(rt == -1 || maxsum[u] < maxsum[rt]) rt = u;
}
void getDis(int u, int pre, int w){
d[pd++] = w;
for(int i = head[u]; ~i; i = e[i].nxt){
int v = e[i].v;
if(used[v] || v == pre) continue;
getDis(v, u, w + e[i].w);
}
}
int calc(int u, int w, int k){
pd = 0;
getDis(u, -1, w);
sort(d, d + pd);
int ret = 0;
int head = 0, tail = pd - 1;
while(head < tail){
while(d[head] + d[tail] >= k && head < tail){
if(d[head] + d[tail] == k) ret++;
tail--;
}
head++;
}
return ret;
}
int dfs(int u, int n, int k){
int rt = -1;
getRoot(u, -1, n, rt);
used[u] = true;
int ans = calc(u, 0, k);
for(int i = head[u]; ~i; i = e[i].nxt){
int v = e[i].v;
if(used[v]) continue;
ans -= calc(v, e[i].w, k);
ans += dfs(v, sum[v], k);
}
return ans;
}
int main(){
int n, q;
while(~scanf("%d%d", &n, &q)){
init();
for(int i = 1; i <= n - 1; i++){
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
addEdge(u, v, w);
addEdge(v, u, w);
}
while(q--){
memset(used, 0, sizeof(used));
int k;
scanf("%d", &k);
puts(dfs(1, n, k) ? "AYE" : "NAY");
}
}
}
洛谷 P2664 - 树上游戏
链接
https://www.luogu.org/problemnew/show/P2664
思路
对于以rt为根的子树，有三种情况
① 以rt为一端，其经过其子树的点，子树的点对他的贡献值
② 以rt的子树中的一点为一端，其经过rt，rt对其造成的贡献值
③ 不经过rt
其中的情况三可以分治解决，因此只考虑如何解决情况一和情况二
记v及其子树中点的总数量为sum[v]，记v点的颜色为color[v]，记颜色color[v]的总贡献值为val[color[v]]，颜色color[v]出现的次数为cnt[color[v]]
对于情况一，若该点在子树中第一次出现，则其对rt的贡献值为sum[v]，因此只需要从rt开始dfs一遍便可计算出子树（包括rt）对rt的贡献值，记为total_sum，同时更新val数组，再计算情况二
对于情况二，先清空子树（不含rt，此处可以cnt[color[rt]]++）对total_sum和val数组的影响，以便计算的经过rt的路径不会被子树所影响，再进行DFS。在DFS的过程中，若遍历到节点u，某颜色第一次出现，则记录不同颜色出现的变量other_tot自增1，rt对u贡献必增加sum[rt] - sum[v]（v为rt的子树），此时rt对u的总贡献中一部分为other_tot * (sum[rt] - sum[v])，另一部分的贡献来自于total_sum减去第一次出现的颜色color[u]的val，这是因为其已被sum[rt] - sum[v]涵盖，不减去会重复计算，因此最终
if((++cnt[color[u]]) == 1){
color_tot++;
total_sum -= val[color[u]];
}
ans[u] += (total_sum + (ll)color_tot * other_sz);
记得回溯时需恢复影响
剩余的情况分治处理即可
最后回来讨论一下为什么需要cnt[color[rt]]++，因为这样可以避免清空子树和计算子树color[rt]第一次出现的影响。color[rt]必然是在rt第一次出现，先++再处理就不会产生影响，而且color[rt]的影响已计入total_sum，计算得到的答案依然是正确的
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 100000 + 15;
typedef long long ll;
const int inf = 0x3f3f3f3f;
struct edge{
int v, nxt;
};
int head[N], tot;
bool used[N];
edge e[N << 1];
int sum[N], maxsum[N], color[N], cnt[N];
ll ans[N], val[N];
inline void init(){
tot = 0;
memset(head, -1, sizeof(head));
memset(ans, 0, sizeof(ans));
}
inline void addEdge(int u, int v){
e[tot] = edge{v, head[u]};
head[u] = tot++;
}
void getRoot(int u, int pre, int size, int& rt){
sum[u] = 1, maxsum[u] = 0;
for(int i = head[u]; ~i; i = e[i].nxt){
int v = e[i].v;
if(used[v] || v == pre) continue;
getRoot(v, u, size, rt);
sum[u] += sum[v];
maxsum[u] = max(maxsum[u], sum[v]);
}
maxsum[u] = max(maxsum[u], size - sum[u]);
if(rt == -1 || maxsum[u] < maxsum[rt]) rt = u;
}
void initTree(int u, int pre){
cnt[color[u]] = val[color[u]] = 0, sum[u] = 1;
for(int i = head[u]; ~i; i = e[i].nxt){
int v = e[i].v;
if(v == pre || used[v]) continue;
initTree(v, u);
sum[u] += sum[v];
}
}
void change(int u, int pre, int flag, ll& total_sum){
if((++cnt[color[u]]) == 1){
total_sum = total_sum + flag * sum[u];
val[color[u]] = val[color[u]] + flag * sum[u];
}
for(int i = head[u]; ~i; i = e[i].nxt){
int v = e[i].v;
if(v == pre || used[v]) continue;
change(v, u, flag, total_sum);
}
cnt[color[u]]--;
}
void calcRoot(int u, int pre, ll& total_sum){
if((++cnt[color[u]]) == 1){
total_sum += sum[u];
val[color[u]] += sum[u];
}
for(int i = head[u]; ~i; i = e[i].nxt){
int v = e[i].v;
if(v == pre || used[v]) continue;
calcRoot(v, u, total_sum);
}
cnt[color[u]]--;
}
void calcSubTree(int u, int pre, int color_tot, int other_sz, ll& total_sum){
if((++cnt[color[u]]) == 1){
color_tot++;
total_sum -= val[color[u]];
}
ans[u] += (total_sum + (ll)color_tot * other_sz);
for(int i = head[u]; ~i; i = e[i].nxt){
int v = e[i].v;
if(v == pre || used[v]) continue;
calcSubTree(v, u, color_tot, other_sz, total_sum);
}
if((--cnt[color[u]]) == 0){
color_tot--;
total_sum += val[color[u]];
}
}
void dfs(int u, ll& total_sum){
used[u] = true, total_sum = 0;
initTree(u, -1);
calcRoot(u, -1, total_sum);
ans[u] += total_sum;
for(int i = head[u]; ~i; i = e[i].nxt){
int v = e[i].v;
if(used[v]) continue;
cnt[color[u]]++;
change(v, u, -1, total_sum);
total_sum -= sum[v];
val[color[u]] -= sum[v];
calcSubTree(v, u, 0, sum[u] - sum[v], total_sum);
change(v, u, 1, total_sum);
total_sum += sum[v];
val[color[u]] += sum[v];
cnt[color[u]]--;
}
for(int i = head[u]; ~i; i = e[i].nxt){
int v = e[i].v;
if(used[v]) continue;
int rt = -1;
getRoot(v, u, sum[v], rt);
dfs(rt, total_sum);
}
}
int main(){
int n;
while(~scanf("%d", &n)){
init();
for(int i = 1; i <= n; i++){
scanf("%d", &color[i]);
}
for(int i = 1; i <= n - 1; i++){
int u, v;
scanf("%d%d", &u, &v);
addEdge(u, v);
addEdge(v, u);
}
int rt = -1;
ll total_sum;
getRoot(1, -1, n, rt);
dfs(rt, total_sum);
for(int i = 1; i <= n; i++){
printf("%lld\n", ans[i]);
}
}
}
洛谷 P3345 - [ZJOI2015]幻想乡战略游戏
链接
https://www.luogu.org/problemnew/show/P3345
思路 —— 动态点分治
首先考虑如何转移答案？
构造点分树，然后爬树高暴力更新，树高logn所以随便搞[滑稽.jpg]
记ans[u][0]为以u为根的点分树块内的答案总贡献，ans[u][1]为以u为根的点分树块内对par[u]的答案的总贡献，val[u]为以u为根的点分树块内的军队数量
那么统计以u为根的答案贡献，只需要一个循环暴力爬树高，边爬边容斥统计答案，边转移根即可。具体来说，记目前循环到根i，那么将根转移到par[i]时，答案贡献增量为(ans[par[i]][0] - ans[i][1])，但是答案是对于根u而言的，因此还需要计算从par[i]到u的答案的增量dist(u, par[i]) * (val[par[i]] - val[i])（自行画图计算），累加答案即可
改变军队的数量只需要暴力爬树高更新ans和val即可
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100100;
const int inf = 0x3f3f3f3f;
typedef long long ll;
struct edge{
int v, w, nxt;
};
int head[N], rthead[N], tot, rttot;
int sum[N], par[N];
int dpt[N], d[N], fa[N][20], maxsum[N];
bool used[N];
edge e[N << 1];
edge rte[N << 1];
ll ans[N][2], val[N];
inline void init(){
tot = rttot = 1;
}
inline int read(){
char ch = getchar(); int x = 0, f = 1;
while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
while('0' <= ch && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
inline void addEdge(int u, int v, int w){
e[tot] = edge{v, w, head[u]};
head[u] = tot++;
}
inline void addRootEdge(int u, int v, int w){
rte[rttot] = edge{v, w, rthead[u]};
rthead[u] = rttot++;
}
void initLCA(int u, int pre){
fa[u][0] = pre;
for(int j = 1; j <= 19; j++){
if(fa[u][j - 1] == 0) break;
fa[u][j] = fa[fa[u][j - 1]][j - 1];
}
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].v;
if(v == pre) continue;
dpt[v] = dpt[u] + 1;
d[v] = d[u] + e[i].w;
initLCA(v, u);
}
}
inline int lca(int u, int v) {
if(dpt[u] < dpt[v]) swap(u, v);
int tmp = dpt[u] - dpt[v];
for(int k = 0, j = 1; j <= tmp; j <<= 1, k++){
if(tmp & j) u = fa[u][k];
}
while(u != v) {
int j = 0;
while(fa[u][j] != fa[v][j]) j++;
if(j) j--;
u = fa[u][j], v = fa[v][j];
}
return u;
}
int getDist(int u, int v){
return d[u] + d[v] - (d[lca(u, v)] << 1);
}
void getRoot(int u, int pre, int size, int& rt){
sum[u] = 1, maxsum[u] = 0;
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].v;
if(v == pre || used[v]) continue;
getRoot(v, u, size, rt);
sum[u] += sum[v];
maxsum[u] = max(maxsum[u], sum[v]);
}
maxsum[u] = max(maxsum[u], size - sum[u]);
if(rt == 0 || maxsum[u] < maxsum[rt]) rt = u;
}
void initTree(int u){
used[u] = true;
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].v;
if(used[v]) continue;
int rt = 0;
getRoot(v, u, sum[v], rt);
par[rt] = u;
addRootEdge(u, v, rt);
initTree(rt);
}
}
ll query(int u){
ll ret = ans[u][0];
for(int i = u; par[i]; i = par[i]){
int d = getDist(u, par[i]);
ret += ans[par[i]][0];
ret -= ans[i][1];
ret += (ll)d * (val[par[i]] - val[i]);
}
return ret;
}
void update(int u, int x){
val[u] += x;
for(int i = u; par[i]; i = par[i]){
int d = getDist(u, par[i]);
ans[par[i]][0] += (ll)x * d;
ans[i][1] += (ll)x * d;
val[par[i]] += x;
}
}
ll work(int u){
ll ret = query(u);
for(int i = rthead[u]; i; i = rte[i].nxt){
int v = rte[i].v;
ll tmp = query(v);
if(tmp < ret){
ret = min(ret, work(rte[i].w));
}
}
return ret;
}
int main(){
int n, q;
while(~scanf("%d%d", &n, &q)){
init();
for(int i = 1; i <= n - 1; i++){
int u = read(), v = read(), w = read();
addEdge(u, v, w);
addEdge(v, u, w);
}
initLCA(1, 0);
int rt = 0;
getRoot(1, 0, n, rt);
par[rt] = 0;
initTree(rt);
while(q--){
int u = read(), x = read();
update(u, x);
printf("%lld\n", work(rt));
}
}
return 0;
}
BZOJ 3730 - 震波
链接
https://cn.vjudge.net/problem/HYSBZ-3730
思路1 —— 点分治 + 线段树
与上题一样，通过暴力爬树高的方法进行更新与查询，并用容斥的方法统计答案，本题因为查询与距离相关，可以考虑对每个节点维护一棵动态开点线段树，将该点分治块中的点以距离为下标，插入其价值，这样便可与上题一样查询与更新
#include <cstdio>
#include <iostream>
#include <cstring>
#define lson l, m
#define rson m + 1, r
using namespace std;
const int N = 100100;
const int inf = 0x3f3f3f3f;
struct edge{
int v, nxt;
};
int w[N], head[N], tot;
int sum[N], par[N];
int dpt[N], fa[N][20], d[N], maxsum[N];
bool used[N];
edge e[N << 1];
int root[N][2];
int ls[N << 6], rs[N << 6], seg[N << 6], segtot;
inline void swap(int &x, int &y) {
if(x == y) return;
x = x^y;
y = x^y;
x = x^y;
}
inline int max(const int& a, const int& b){
return a > b ? a : b;
}
inline char get(void) {
static char buf[1000000], *p1 = buf, *p2 = buf;
if (p1 == p2) {
p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin);
if (p1 == p2) return EOF;
}
return *p1++;
}
inline void read(int &x) {
x = 0; static char c; bool minus = false;
for (; !(c >= '0' && c <= '9'); c = get()) if (c == '-') minus = true;
for (; c >= '0' && c <= '9'; x = x * 10 + c - '0', c = get()); if (minus) x = -x;
}
inline void write(int x) {
if (!x) return (void) puts("0");
if (x < 0) putchar('-'), x = -x;
static short s[12], t;
while (x) s[++t] = x % 10, x /= 10;
while (t) putchar('0' + s[t--]);
putchar('\n');
}
inline void addEdge(int u, int v){
e[tot] = edge{v, head[u]};
head[u] = tot++;
}
// START -- LCA and dist
void initLCA(int u, int pre){
fa[u][0] = pre;
for(int j = 1; j <= 19; j++){
if(fa[u][j - 1] == 0) break;
fa[u][j] = fa[fa[u][j - 1]][j - 1];
}
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].v;
if(v == pre) continue;
dpt[v] = dpt[u] + 1;
initLCA(v, u);
}
}
inline int lca(int x, int y) {
if (dpt[x] < dpt[y]) swap(x, y);
int tmp = dpt[x] - dpt[y];
for (int k = 0, j = 1; j <= tmp; j <<= 1, k++)
if (tmp & j) x = fa[x][k];
while (x != y) {
int j = 0;
while (fa[x][j] != fa[y][j]) j++;
if(j) j--;
x = fa[x][j], y = fa[y][j];
}
return x;
}
int getDist(int u, int v){
return dpt[u] + dpt[v] - (dpt[lca(u, v)] << 1);
}
// END -- LCA and dist
// START -- SegmentTree
inline void newNode(int& o){
o = segtot++;
}
void push(int& o, int pos, int val, int l, int r){
if(o == 0) newNode(o);
seg[o] += val;
if(l == r) return;
int m = (l + r) >> 1;
if(pos <= m) push(ls[o], pos, val, lson);
else push(rs[o], pos, val, rson);
}
int query(int o, int ql, int qr, int l, int r){
if(o == 0) return 0;
if(ql <= l && r <= qr){
return seg[o];
}
int m = (l + r) >> 1;
int ans = 0;
if(ql <= m) ans += query(ls[o], ql, qr, lson);
if(m < qr) ans += query(rs[o], ql, qr, rson);
return ans;
}
// END -- SegmentTree
// START -- Core
void getRoot(int u, int pre, int size, int& rt){
sum[u] = 1, maxsum[u] = 0;
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].v;
if(v == pre || used[v]) continue;
getRoot(v, u, size, rt);
sum[u] += sum[v];
maxsum[u] = max(maxsum[u], sum[v]);
}
maxsum[u] = max(maxsum[u], size - sum[u]);
if(rt == 0 || maxsum[u] < maxsum[rt]) rt = u;
}
void setSegTree(int u, int pre, int n, int rt, int idx){
push(root[rt][idx], d[u], w[u], 0, n);
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].v;
if(v == pre || used[v]) continue;
d[v] = d[u] + 1;
setSegTree(v, u, n, rt, idx);
}
}
void initTree(int u, int n){
used[u] = true, d[u] = 0;
setSegTree(u, 0, n, u, 0);
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].v;
if(used[v]) continue;
int rt = 0;
d[v] = 1;
getRoot(v, u, sum[v], rt);
setSegTree(v, u, n, rt, 1);
par[rt] = u;
initTree(rt, n);
}
}
int solveQuery(int u, int n, int d){
int ret = query(root[u][0], 0, d, 0, n);
for(int i = u; par[i] != 0; i = par[i]){
int k = getDist(u, par[i]);
if(d - k < 0) continue;
ret += query(root[par[i]][0], 0, d - k, 0, n);
ret -= query(root[i][1], 0, d - k, 0, n);
}
return ret;
}
void solveUpdate(int u, int n, int delta){
push(root[u][0], 0, delta, 0, n);
for(int i = u; par[i] != 0; i = par[i]){
int d = getDist(u, par[i]);
push(root[par[i]][0], d, delta, 0, n);
push(root[i][1], d, delta, 0, n);
}
}
// END -- Core
inline void init(){
tot = segtot = 1;
}
int main(){
int n, q;
read(n), read(q);
init();
for(int i = 1; i <= n; i++){
read(w[i]);
}
for(int i = 1; i <= n - 1; i++){
int u, v;
read(u), read(v);
addEdge(u, v);
addEdge(v, u);
}
initLCA(1, 0);
int u = 0;
getRoot(1, 0, n, u);
par[u] = 0;
initTree(u, n);
int lstans = 0;
while(q--){
int op, x, y;
read(op), read(x), read(y);
x ^= lstans, y ^= lstans;
if(op){
solveUpdate(x, n, y - w[x]);
w[x] = y;
}else{
lstans = solveQuery(x, n, y);
write(lstans);
}
}
return 0;
}
思路2 —— 点分治 + 树状数组
因为每次查询的区间都是[0,k]，故可用树状数组代替线段树，加快程序运行效率
树状数组貌似不存在动态开点的说法吧，但是可用vector开不定长数组，使用resize即可，不用担心爆内存
#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int N = 100100;
const int inf = 0x3f3f3f3f;
struct edge{
int v, nxt;
};
int w[N], head[N], tot;
int sum[N], par[N];
int dpt[N], fa[N][20], d[N], maxsum[N];
bool used[N];
edge e[N << 1];
vector<int> tree[N][2];
inline void swap(int &x, int &y) {
if(x == y) return;
x = x^y;
y = x^y;
x = x^y;
}
inline int max(const int& a, const int& b){
return a > b ? a : b;
}
inline char get(void) {
static char buf[1000000], *p1 = buf, *p2 = buf;
if (p1 == p2) {
p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin);
if (p1 == p2) return EOF;
}
return *p1++;
}
inline void read(int &x) {
x = 0; static char c; bool minus = false;
for (; !(c >= '0' && c <= '9'); c = get()) if (c == '-') minus = true;
for (; c >= '0' && c <= '9'; x = x * 10 + c - '0', c = get()); if (minus) x = -x;
}
inline void write(int x) {
if (!x) return (void) puts("0");
if (x < 0) putchar('-'), x = -x;
static short s[12], t;
while (x) s[++t] = x % 10, x /= 10;
while (t) putchar('0' + s[t--]);
putchar('\n');
}
inline void addEdge(int u, int v){
e[tot] = edge{v, head[u]};
head[u] = tot++;
}
// START -- LCA and dist
void initLCA(int u, int pre){
fa[u][0] = pre;
for(int j = 1; j <= 19; j++){
if(fa[u][j - 1] == 0) break;
fa[u][j] = fa[fa[u][j - 1]][j - 1];
}
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].v;
if(v == pre) continue;
dpt[v] = dpt[u] + 1;
initLCA(v, u);
}
}
inline int lca(int x, int y) {
if(dpt[x] < dpt[y]) swap(x, y);
int tmp = dpt[x] - dpt[y];
for(int k = 0, j = 1; j <= tmp; j <<= 1, k++)
if (tmp & j) x = fa[x][k];
while(x != y) {
int j = 0;
while (fa[x][j] != fa[y][j]) j++;
if(j) j--;
x = fa[x][j], y = fa[y][j];
}
return x;
}
int getDist(int u, int v){
return dpt[u] + dpt[v] - (dpt[lca(u, v)] << 1);
}
// END -- LCA and dist
// START -- BIT
inline int lowbit(int idx){ return (idx & -idx); }
int getSum(vector<int>& vec, int idx){
idx++;
if(idx >= vec.size()) idx = vec.size() - 1;
int sum;
for(sum = 0; idx > 0; idx -= lowbit(idx)){
sum += vec[idx];
}
return sum;
}
void update(vector<int>& vec, int idx, int val){
idx++;
while(idx < vec.size()){
vec[idx] += val;
idx += (idx & -idx);
}
}
// END -- BIT
// START -- Core
void getRoot(int u, int pre, int size, int& rt){
sum[u] = 1, maxsum[u] = 0;
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].v;
if(v == pre || used[v]) continue;
getRoot(v, u, size, rt);
sum[u] += sum[v];
maxsum[u] = max(maxsum[u], sum[v]);
}
maxsum[u] = max(maxsum[u], size - sum[u]);
if(rt == 0 || maxsum[u] < maxsum[rt]) rt = u;
}
void setSegTree(int u, int pre, int rt, int idx){
update(tree[rt][idx], d[u], w[u]);
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].v;
if(v == pre || used[v]) continue;
d[v] = d[u] + 1;
setSegTree(v, u, rt, idx);
}
}
void initTree(int u, int n){
used[u] = true, d[u] = 0;
setSegTree(u, 0, u, 0);
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].v;
if(used[v]) continue;
int rt = 0;
d[v] = 1;
getRoot(v, u, sum[v], rt);
tree[rt][0].resize(sum[v] + 5);
tree[rt][1].resize(sum[v] + 5);
setSegTree(v, u, rt, 1);
par[rt] = u;
initTree(rt, n);
}
}
int solveQuery(int u, int d){
int ret = getSum(tree[u][0], d);
for(int i = u; par[i] != 0; i = par[i]){
int k = getDist(u, par[i]);
if(d - k < 0) continue;
ret += getSum(tree[par[i]][0], d - k);
ret -= getSum(tree[i][1], d - k);
}
return ret;
}
void solveUpdate(int u, int delta){
update(tree[u][0], 0, delta);
for(int i = u; par[i] != 0; i = par[i]){
int d = getDist(u, par[i]);
update(tree[par[i]][0], d, delta);
update(tree[i][1], d, delta);
}
}
// END -- Core
inline void init(){
tot = 1;
}
int main(){
int n, q;
read(n), read(q);
init();
for(int i = 1; i <= n; i++){
read(w[i]);
}
for(int i = 1; i <= n - 1; i++){
int u, v;
read(u), read(v);
addEdge(u, v);
addEdge(v, u);
}
initLCA(1, 0);
int u = 0;
getRoot(1, 0, n, u);
tree[u][0].resize(n + 5);
par[u] = 0;
initTree(u, n);
int lstans = 0;
while(q--){
int op, x, y;
read(op), read(x), read(y);
x ^= lstans, y ^= lstans;
if(op){
solveUpdate(x, y - w[x]);
w[x] = y;
}else{
lstans = solveQuery(x, y);
write(lstans);
}
}
return 0;
}
