一半 MLE 了，疑似爆栈了(？

救救孩子.jpg

#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio> 

#define int long long 

using namespace std;

const int N=2e6+100;
int n,q;
int h[N],e[2*N],nxt[2*N],idx;
int val[N];
bool st[N];
int cnt=0;
int maxdep,maxdep2;

struct Son{
	int wc,from,dis;
};
vector<Son> son[N];
vector<int> f1[N],f2[N];
int father[N];

int lowbit(int x){
	return x&-x;
}

void add(int a,int b){
	nxt[idx]=h[a],e[idx]=b,h[a]=idx++;
}

void get_depth(int u,int fa,int dep,int wc,int id){
	maxdep2=max(maxdep2,dep);
	son[u].push_back({wc,id,dep});
	for(int i=h[u];~i;i=nxt[i]){
		int v=e[i];
		if(st[v] || v==fa)
			continue;
		get_depth(v,u,dep+1,wc,id);
	}
}

int get_size(int u,int fa){
	if(st[u])
		return 0;
	int res=1;
	for(int i=h[u];~i;i=nxt[i]){
		if(e[i]!=fa)
			res+=get_size(e[i],u);
	}
	return res;
}

int get_wc(int u,int fa,int tot,int& wc){
	if(st[u])
		return 0;
	int sum=1,ms=0;
	for(int i=h[u];~i;i=nxt[i]){
		int v=e[i];
		if(v!=fa)
			continue;
		int t=get_wc(v,u,tot,wc);
		ms=max(ms,t);
		sum+=t;
	}
	ms=max(ms,tot-sum);
	if(ms<=tot/2)
		wc=u;
	return sum; 
}

void build(int u){
	if(st[u])
		return ;
	get_wc(u,0,get_size(u,0),u);
	son[u].push_back({u,0,0});
//	cout<<u<<endl;
//	cout<<"QWQ"<<u<<endl;
	st[u]=1;
	maxdep=0;
	for(int i=h[u];~i;i=nxt[i]){
		int v=e[i];
		if(!st[v]){
			maxdep2=0;
			++cnt;
			get_depth(v,u,1,u,cnt);
			maxdep=max(maxdep,maxdep2);
			f2[cnt].resize(maxdep2+2);
		}
	}
	f1[u].resize(maxdep+2);
	for(int i=h[u];~i;i=nxt[i]){
		int v=e[i];
		if(st[v])
			continue;
		build(v);
	}
}

void update1(int t,int x,int val){
	for(int i=x+1;i<f1[t].size();i+=lowbit(i))
		f1[t][i]+=val;
}

int query1(int t,int x){
	int res=0;
	x=min(x+1,(int)(f1[t].size()-1));
	for(int i=x;i>=1;i-=lowbit(i))
		res+=f1[t][i];
	return res;
}

void update2(int t,int x,int val){
	for(int i=x+1;i<f2[t].size();i+=lowbit(i))
		f2[t][i]+=val;
}

int query2(int t,int x){
	int res=0;
	x=min(x+1,(int)(f2[t].size()-1));
	for(int i=x;i>=1;i-=lowbit(i))
		res+=f2[t][i];
	return res;
}

void modify(int u,int val){
//	cout<<u<<" "<<val<<endl;
	for(auto& t:son[u]){
		update1(t.wc,t.dis,val);
		if(t.from)
			update2(t.from,t.dis,val);
	}
}

int ask(int u,int k){
	int ans=0;
	for(auto& t:son[u]){
		if(k<t.dis)
			continue;
		ans+=query1(t.wc,k-t.dis);
	//	cout<<"QWQ"<<ans<<endl;
		ans-=query2(t.from,k-t.dis);
	//	cout<<"QWQ"<<ans<<endl;
	}
	return ans;
}

signed main(){
	freopen("P6329_1.in","r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	memset(h,-1,sizeof(h));
	cin>>n>>q;
	for(int i=1;i<=n;++i)
		cin>>val[i];
	for(int i=1;i<n;++i){
		int a,b;
		cin>>a>>b;
		add(a,b);
		add(b,a);
	}
	build(1);
	for(int i=1;i<=n;++i)
		modify(i,val[i]);
	int lasans=0;
	while(q--){
		int op,x,y;
		cin>>op>>x>>y;
		x^=lasans,y^=lasans; 
		if(op){
			modify(x,y-val[x]);
			val[x]=y;
		}
		else{
			cout<<(lasans=ask(x,y))<<endl;
		}
	}
	return 0;
}