众所周知，我写题从来不写正解。

所以我来教大家如何 $O(n^2)$ 通过此题。

先看代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,a[200005],u,v,fdfn[200005],dfn[200005],dfns,dep[200005],lk[200005],rk[200005],lk2[200005],rk2[200005];
vector<int>vt[200005];
int op,x;
int xa[200005],xb[200005],ta,tb;
int q[200005];
bool f[200005];
struct tree{
	int tree[800005],tag[800005];
	void make_tree(int id,int l,int r,bool f){
		if(l==r){
			if(f)tree[id] = a[xa[l]];
			else tree[id] = a[xb[l]];
			return;
		}
		make_tree(id*2,l,(l+r)/2,f);
		make_tree(id*2+1,(l+r)/2+1,r,f);
		tree[id] = tree[id*2]+tree[id*2+1];
		return;
	}
	void addtag(int id,int l,int r,int d){
		tag[id]+=d;
		tree[id]+=d*(r-l+1);
		return;
	}
	void push_down(int id,int l,int r){
		if(tag[id]){
			int md = (l+r)/2;
			addtag(id*2,l,(l+r)/2,tag[id]);
			addtag(id*2+1,(l+r)/2+1,r,tag[id]);
			tag[id] = 0;
		}
		return;
	}
	void update(int l,int r,int id,int idl,int idr,int d){
		if(l<=idl&&r>=idr){
			addtag(id,idl,idr,d);
			return;
		}
		push_down(id,idl,idr);
		int md = (idl+idr)/2;
		if(l<=md)update(l,r,id*2,idl,md,d);
		if(r>md)update(l,r,id*2+1,md+1,idr,d);
		tree[id] = tree[id*2]+tree[id*2+1];
		return;
	}
	int query(int l,int r,int id,int idl,int idr){
		if(l<=idl&&r>=idr)return tree[id];
		push_down(id,idl,idr);
		int ans = 0,md = (idl+idr)/2;
		if(l<=md)ans+=query(l,r,id*2,idl,md);
		if(r>md)ans+=query(l,r,id*2+1,md+1,idr);
		return ans;
	}
}tr,tr2;
void dfs(int x,int fa){
	dfn[x] = ++dfns;
	fdfn[dfns] = x;
	dep[dfns] = dep[dfn[fa]]+1;
	lk2[dfns] = lk[dfns] = dfns;
	for(int i = 0;i<vt[x].size();i++){
		int pv = vt[x][i];
		if(pv==fa)continue;
		dfs(pv,x);
	}
	rk2[dfn[x]] = rk[dfn[x]] = dfns;
	return;
}
signed main(){
	cin >> n >> m;
	for(int i = 1;i<=n;i++)cin >> a[i];
	for(int i = 1;i<n;i++){
		cin >> u >> v;
		vt[u].push_back(v);
		vt[v].push_back(u);
	}
	dfs(1,0);
	for(int i = 1;i<=dfns;i++){
		if(dep[i]%2)xa[++ta] = fdfn[i],f[i] = 1,q[i] = ta;
		else xb[++tb] = fdfn[i],f[i] = 0,q[i] = tb;
	}
	tr.make_tree(1,0,ta,1);
	tr2.make_tree(1,0,tb,0);
	for(int i = 1;i<=dfns;i++){
		while(lk[i]<=dfns&&dep[lk[i]]%2==0)lk[i]++;
		while(lk2[i]<=dfns&&dep[lk2[i]]%2==1)lk2[i]++;
		while(rk[i]>=lk[i]&&dep[rk[i]]%2==0)rk[i]--;
		while(rk2[i]>=lk2[i]&&dep[rk2[i]]%2==1)rk2[i]--;
		if(rk[i]<lk[i])rk[i] = 0;
		else rk[i] = q[rk[i]];
		if(rk2[i]<lk2[i])rk2[i] = 0;
		else rk2[i] = q[rk2[i]];
		if(lk[i]>dfns)lk[i] = 0;
		else lk[i] = q[lk[i]];
		if(lk2[i]>dfns)lk2[i] = 0;
		else lk2[i] = q[lk2[i]];
	}
	while(m--){
		cin >> op >> x;
		x = dfn[x];
		if(op==1){
			cin >> v;
			if(dep[x]%2)tr.update(lk[x],rk[x],1,0,ta,v);
			else tr.update(lk[x],rk[x],1,0,ta,-v);
			if(dep[x]%2)tr2.update(lk2[x],rk2[x],1,0,tb,-v);
			else tr2.update(lk2[x],rk2[x],1,0,tb,v);
		}
		else{
			if(f[x])cout << tr.query(q[x],q[x],1,0,ta) << "\n";
			else cout << tr2.query(q[x],q[x],1,0,tb) << "\n";
		}
	}
	return 0;
}

显然的，对于这道题，这个代码中的这个部分：

for(int i = 1;i<=dfns;i++){
	while(lk[i]<=dfns&&dep[lk[i]]%2==0)lk[i]++;
	while(lk2[i]<=dfns&&dep[lk2[i]]%2==1)lk2[i]++;
	while(rk[i]>=lk[i]&&dep[rk[i]]%2==0)rk[i]--;
	while(rk2[i]>=lk2[i]&&dep[rk2[i]]%2==1)rk2[i]--;
	if(rk[i]<lk[i])rk[i] = 0;
	else rk[i] = q[rk[i]];
	if(rk2[i]<lk2[i])rk2[i] = 0;
	else rk2[i] = q[rk2[i]];
	if(lk[i]>dfns)lk[i] = 0;
	else lk[i] = q[lk[i]];
	if(lk2[i]>dfns)lk2[i] = 0;
	else lk2[i] = q[lk2[i]];
}

可以卡至 $O(n^2)$，但显然的，我通过了，所以数据过水。