RT，求助，除了第三个点全部RE，救救孩子。

另附：

int sz=(siz[to[i]]<siz[now])?siz[now]:(S-siz[now]);

题解这样写可以得满分

int sz=(siz[to[i]]<siz[now])?siz[to[i]]:(S-siz[now]);

这样写就分数随机（每次测分数都不一样）

有谁能解答一下吗谢谢。

#include<bits/stdc++.h>
#define N 1000010
#define M 5000010
#define mid (l+r)/2
using namespace std;
int cnt,head[N],to[N],nxt[N];
void insert(int u,int v) {
	cnt++;
	to[cnt]=v;
	nxt[cnt]=head[u];
	head[u]=cnt;
}
int read() {
	int res=0,f=1;char ch=getchar();
	while(!isdigit(ch)) f=ch=='-'?-1:1,ch=getchar();
	while(isdigit(ch)) res=res*10+ch-'0',ch=getchar();
	return f*res;
}
int n,m,dep[N],vis[N],t[N][22],a[N];
void dfs0(int now,int fa) {
	t[now][0]=fa;
	for(int k=1; k<20; k++) t[now][k]=t[t[now][k-1]][k-1];
	for(int i=head[now]; i; i=nxt[i]) if(to[i]!=fa) {
		dep[to[i]]=dep[now]+1;
		dfs0(to[i],now);
	} 
}
int lca(int a1,int a2) {
	if(dep[a1]<dep[a2]) swap(a1,a2);
	for(int i=19; i>=0; i--)
	    if(dep[a1]-(1<<i)>=dep[a2]) a1=t[a1][i];
	if(a1==a2) return a1;
	for(int i=19; i>=0; i--)
	    if(t[a1][i]!=t[a2][i]) a1=t[a1][i],a2=t[a2][i];
	return t[a1][0];
}
int siz[N],son[N],rt,df[N];
void gtrt(int now,int fa,int S) {
	siz[now]=1,son[now]=0;
	for(int i=head[now]; i; i=nxt[i]) 
	    if(to[i]!=fa&&!vis[to[i]]) {
	    	gtrt(to[i],now,S);
	    	siz[now]+=siz[to[i]];
	    	son[now]=max(son[now],siz[to[i]]);
	    } 
	son[now]=max(son[now],S-siz[now]);
	if(son[now]<son[rt]) rt=now;
}
void solve(int now,int S) {
	vis[now]=1;
	for(int i=head[now]; i; i=nxt[i]) if(!vis[to[i]]) {
		rt=0;int sz=(siz[to[i]]<siz[now])?siz[now]:(S-siz[now]);
		gtrt(to[i],now,sz),df[rt]=now,solve(rt,sz);
	}
}
struct segtree{
	int rt[N],ncnt,son[N][2];
	vector<int> s1,s2,val;
	void init() {
		memset(rt,0,sizeof(rt)),ncnt=0;
		s1.push_back(0),s2.push_back(0),val.push_back(0);
	}
	void New() {
		s1.push_back(0),s2.push_back(0),val.push_back(0);
	}
	void modify(int &k,int l,int r,int p,int num) {
		if(!k) k=++ncnt,New();
		if(l==r) {val[k]+=num;return ;}
		if(p<=mid) modify(son[k][0],l,mid,p,num);
		else modify(son[k][1],mid+1,r,p,num);
		val[k]=val[son[k][0]]+val[son[k][1]];
	}
	int query(int k,int l,int r,int L,int R) {
		if(!k) return 0;
		if(L<=l&&r<=R) return val[k];
		int res=0;
		if(L<=mid) res+=query(son[k][0],l,mid,L,R);
		if(R>mid) res+=query(son[k][1],mid+1,r,L,R);
		return res;
	}
}w1,w2;
int dis(int a1,int a2) {
	return dep[a1]+dep[a2]-2*dep[lca(a1,a2)];
}
void modify(int id,int val) {
	int now=id;
	while(now) {
		int fa=df[now];
		w1.modify(w1.rt[now],0,n-1,dis(now,id),val);
		if(fa) w2.modify(w2.rt[now],0,n-1,dis(fa,id),val);
		now=fa;
	}
}
int query(int id,int k) {
	int res=0;
	int now=id,las=0;
	while(now) {
		int d=dis(id,now);
		if(d>k) {
			las=now;
			now=df[now];
		}
		res+=w1.query(w1.rt[now],0,n-1,0,k-d);
		if(las) res-=w2.query(w2.rt[las],0,n-1,0,k-d);
		las=now,now=df[now];
	}
	return res;
}
int main()
 {
 	n=read(),m=read();w1.init(),w2.init();
 	for(int i=1; i<=n; i++) a[i]=read();
 	for(int i=1; i<n; i++) {
 		int u=read(),v=read();
 		insert(u,v);
 		insert(v,u);
 	}
 	dfs0(1,0);
 	son[0]=n+1,gtrt(1,0,n);
 	solve(rt,n);
 	for(int i=1; i<=n; i++) modify(i,a[i]);
 	int las=0;
 	for(int i=1; i<=m; i++) {
 		int opt=read(),x=read(),y=read();
 		x^=las,y^=las;
 		if(!opt) {las=query(x,y);printf("%d\n",las);}
 		else modify(x,y-a[x]),a[x]=y;
 	}
	return 0;
}