Description：

一棵树，节点有权值，支持修改权值和询问与某个点距离不超过 $k$ 的点的权值和。

$1\le n \le 100000$

Solution：

动态点分治，先把点分树建出来，按照套路每个点应该维护两个东西，一个表示这个点的值，一个表示这个点对父亲的贡献，这里以距离为下标维护两棵线段树，修改和查询像‘幻想乡战略游戏’一样做就行了。注意下标从 $0$ 开始，线段树动态开点。

这个代码 $RE$ 了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 100010

#define INF 0x3f3f3f3f

int val[MAXN];

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

int top[MAXN],siz[MAXN],dad[MAXN],son[MAXN],dep[MAXN];

void dfs1(int k,int depth)

{

	siz[k] = 1;dep[k] = depth;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != dad[k])

		{

			dad[e[i].to] = k;

			dfs1(e[i].to,depth + 1);

			siz[k] += siz[e[i].to];

			if(son[k] == 0 || siz[e[i].to] > siz[son[k]])

			{

				son[k] = e[i].to;

			}

		}

	}

	return;

}

void dfs2(int k,int tp)

{

	top[k] = tp;

	if(son[k] == 0)return;

	dfs2(son[k],tp);

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != dad[k] && e[i].to != son[k])

		{

			dfs2(e[i].to,e[i].to);

		}

	}

	return;

}

int LCA(int a,int b)

{

	while(top[a] != top[b])

	{

		if(dep[top[a]] < dep[top[b]])swap(a,b);

		a = dad[top[a]];

	}

	return dep[a] < dep[b] ? a : b;

}

int dis(int a,int b){return dep[a] + dep[b] - 2 * dep[LCA(a,b)];}

int size[MAXN],d[MAXN],root,s;

bool v[MAXN];

void getroot(int k,int f)

{

	size[k] = 1;d[k] = 0;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(v[e[i].to] || e[i].to == f)continue;

		getroot(e[i].to,k);

		size[k] += size[e[i].to];

		if(size[e[i].to] > d[k])d[k] = size[e[i].to];

	}

	d[k] = max(d[k],s - d[k]);

	if(d[k] < d[root])root = k;

	return;

}

int fa[MAXN];

void divide(int k)

{

	v[k] = true;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(v[e[i].to])continue;

		root = 0;s = size[e[i].to];

		getroot(e[i].to,0);

		fa[root] = k;

		divide(root);

	}

	return;

}

struct node

{

	int lc,rc;

	int sum;

	node(){lc = rc = sum = 0;}

}t[MAXN * 200];

int ptr = 0;

int newnode(){return ++ptr;}

int root1[MAXN],root2[MAXN];

#define mid ((l + r) >> 1)

void add(int &rt,int p,int k,int l,int r)

{

	if(rt == 0)rt = newnode();

	if(l == r){t[rt].sum += k;return;}

	if(p <= mid)add(t[rt].lc,p,k,l,mid);

	else add(t[rt].rc,p,k,mid + 1,r);

	t[rt].sum = t[t[rt].lc].sum + t[t[rt].rc].sum;

	return;

}

int sum(int rt,int L,int R,int l,int r)

{

	if(L > R)return 0; 

	if(rt == 0)return 0;

	if(L <= l && r <= R)return t[rt].sum;

	int res = 0;

	if(L <= mid)res += sum(t[rt].lc,L,R,l,mid);

	if(R > mid)res += sum(t[rt].rc,L,R,mid + 1,r);

	return res;

}

void modify(int k,int delta)

{

	add(root1[k],0,delta,0,n);

	for(int i = k;fa[i] != 0;i = fa[i])

	{

		add(root1[fa[i]],dis(k,fa[i]),delta,0,n);

		add(root2[i],dis(k,fa[i]),delta,0,n);

	}

	return;

}

int query(int p,int k)

{

	int res = sum(root1[p],0,k,0,n);

	for(int i = p;fa[i] != 0;i = fa[i])

	{

		res += sum(root1[fa[i]],0,k - dis(p,fa[i]),0,n) - sum(root2[i],0,k - dis(p,fa[i]),0,n);

	}

	return res;

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)scanf("%d",&val[i]);

	int a,b,c;

	for(int i = 1;i < n;++i)

	{

		scanf("%d%d",&a,&b);

		add(a,b);

	}

	d[0] = INF;root = 0;s = n;

	getroot(1,0);

	divide(root);

	dfs1(1,1);dfs2(1,1);

	int lastans = 0;

	for(int i = 1;i <= n;++i)modify(i,val[i]);

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%d",&a,&b,&c);

		b ^= lastans;c ^= lastans;

		if(a == 1)

		{

			modify(b,c - val[b]);

			val[b] = c;

		}

		else

		{

			printf("%d\n",lastans = query(b,c));

		}

	}

	return 0;

}