rt，提供我自己加了数据的一道题，请问这道题线段树 + 树链剖分的做法可过吗 /ll /ll

或者还可以帮我卡一卡qwq

#include<bits/stdc++.h>
#define int long long
#define maxn 1000005
using namespace std;
int n,m,r,val[maxn],cnt,head[maxn];
int fa[maxn],son[maxn],num[maxn],fnum[maxn],top[maxn],deep[maxn],siz[maxn];
struct fdfdfd{
	int flag,sum,l,r,len;
}a[maxn<<2];
struct node{
	int next,to;
}e[maxn<<1];
inline void read(int &a){
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-'){
			w=-1;
		}
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		s=s*10+ch-'0';
		ch=getchar();
	}
	a=s*w;
}
inline void write(int &a){
	if(a<0){
		putchar('-');
		a=-a;
	}
	if(a>=10){
		long long ovo=a/10;
		write(ovo);
	}
	putchar(a%10+'0');
}
void addedge(int x,int y){
	e[++cnt].to=y; 
	e[cnt].next=head[x]; 
	head[x]=cnt;
}
void dfs1(int u,int pre){
	fa[u]=pre; 
	siz[u]=1; 
	deep[u]=deep[pre]+1;
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].to;
		if(v==pre){
			continue;
		}
		dfs1(v,u); 
		siz[u]+=siz[v];
		if(son[u]==-1||siz[v]>siz[son[u]]){
			son[u]=v;
		}
	}
}
void dfs2(int u,int topp){
	top[u]=topp; 
	num[u]=++cnt; 
	fnum[cnt]=u;
	if(son[u]!=-1){
		dfs2(son[u],topp);
	}
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].to;
		if(v!=fa[u]&&v!=son[u]){
			dfs2(v,v);
		}
	}
}
void pushup(int x){
	a[x].sum=a[x<<1].sum+a[x<<1|1].sum;
}
void pushdown(int x){
	if(a[x].flag==0){
		return;
	}
	a[x<<1].flag+=a[x].flag; 
	a[x<<1].sum+=a[x].flag*a[x<<1].len;
	a[x<<1|1].flag+=a[x].flag; 
	a[x<<1|1].sum+=a[x].flag*a[x<<1|1].len;
	a[x].flag=0;
}
void build(int x,int left,int right){
	a[x].l=left; 
	a[x].r=right; 
	a[x].len=right-left+1;
	if(left==right){
		a[x].sum=val[fnum[left]]; 
		return;
	}
	int mid=(left+right)>>1;
	build(x<<1,left,mid); 
	build(x<<1|1,mid+1,right);
	pushup(x);
}
void modify(int x,int left,int right,int d)
{
	if(a[x].r<left||a[x].l>right){
		return;
	}
	if(left<=a[x].l&&right>=a[x].r){
		a[x].flag+=d;
		a[x].sum+=a[x].len*d; 
		return;
	}
	pushdown(x);
	modify(x<<1,left,right,d);
	modify(x<<1|1,left,right,d);
	pushup(x);
}
void change_uv(int u,int v,int k)
{
	while(top[u]!=top[v]){
		if(deep[top[u]]<deep[top[v]]){
			swap(u,v);
		}
		modify(1,num[top[u]],num[u],k);
		u=fa[top[u]];
	}
	if(deep[u]>deep[v]){
		swap(u,v);
	}
	modify(1,num[u],num[v],k);
}
int query(int x,int left,int right)
{
	if(a[x].r<left||a[x].l>right){
		return 0;
	}
	if(left<=a[x].l&&right>=a[x].r){
		return a[x].sum;
	}
	pushdown(x);
	return query(x<<1,left,right)+query(x<<1|1,left,right);
}
signed main(){
	memset(son,-1,sizeof(son));
	read(n);
	read(m);
	read(r);
	for(int i=1;i<=n;i++){
		read(val[i]);
	}
	for(int i=1;i<n;i++){
		int u,v;
		read(u);
		read(v);
		addedge(u,v);
		addedge(v,u);
	}
	dfs1(r,0); 
	cnt=0; 
	dfs2(r,r); 
	build(1,1,n);
	while(m--){
		int opt,a,b,x; 
		read(opt);
		read(a);
		if(opt==1){
			read(b);
			read(x);
			change_uv(a,b,x);
		}
		else if(opt==2){
			int lol=query(1,num[a],num[a]);
			write(lol);
			putchar('\n');
		}
		else{
			int lol=query(1,num[a],num[a]+siz[a]-1);
			write(lol);
			putchar('\n');
		}
	}
	return 0;
}