样例输入

5
1 2
1 3 
2 4
2 5
1 2 3 4 5
5
1 2
3 1
2 3 10
1 1
3 1

样例输出

9
7

数据范围

$n,q\le 2\times 10^5,a_{i},y\le 10^9$

我的代码

思路是用DFS序将子树修改转换为区间修改，然后用线段树维护

#include<iostream>
#include<cmath>
using namespace std;
const int N=2e5+5,M=2e5+5;
int n,tot,head[N],nxt[M],ver[M],q,num,f[N<<1];
long long a[N];
int dfn1[N],dfn2[N];
bool vis[N];
struct tree
{
	int l,r;
	long long sum,Max;
	#define l(x) c[x].l
	#define r(x) c[x].r
	#define sum(x) c[x].sum
	#define Max(x) c[x].Max
}c[N<<4];
void dfs(int x)
{
	vis[x]=true;
	num++;
	dfn1[x]=num;
	f[num]=a[x];
	for(int i=head[x];i;i=nxt[i])
	{
		int y=ver[i];
		if(!vis[y])
			dfs(y);
	}
	num++;
	dfn2[x]=num;
	f[num]=a[x];
}
void add(int x,int y)
{
	tot++;
	ver[tot]=y;
	nxt[tot]=head[x];
	head[x]=tot;
}
void build(int p,int l,int r)
{
	l(p)=l,r(p)=r;
	if(l==r)
	{
		Max(p)=f[l];
		sum(p)=f[l];
		return;
	}
	int mid=(l+r)>>1;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	Max(p)=max(Max(p*2),Max(p*2+1));
	sum(p)=sum(p*2)+sum(p*2+1);
}
void change(int p,int l,int r)
{
	if(l(p)==r(p))
	{
		sum(p)=(int)(sqrt(sum(p)));
		Max(p)=(int)(sqrt(Max(p)));
		return;
	}
	int mid=(l(p)+r(p))>>1;
	if(l<=mid&&Max(p*2)>1)
		change(p*2,l,r);
	if(r>mid&&Max(p*2+1)>1)
		change(p*2+1,l,r);
	Max(p)=max(Max(p*2),Max(p*2+1));
	sum(p)=sum(p*2)+sum(p*2+1);
}
void change2(int p,int x)
{
	if(l(p)==r(p))
	{
		Max(p)=x;
		sum(p)=x;
		return;
	}
	int mid=(l(p)+r(p))>>1;
	if(x<=mid)
		change2(p*2,x);
	else
		change2(p*2+1,x);
	Max(p)=max(Max(p*2),Max(p*2+1));
	sum(p)=sum(p*2)+sum(p*2+1);
}
long long ask(int p,int l,int r)
{
	if(l<=l(p)&&r>=r(p))
		return sum(p);
	int mid=(l(p)+r(p))>>1;
	long long ans=0;
	if(l<=mid)
		ans+=ask(p*2,l,r);
	if(r>mid)
		ans+=ask(p*2+1,l,r);
	return ans;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);
		add(v,u);
	}
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	dfs(1);
	build(1,1,num);
	scanf("%d",&q);
	while(q--)
	{
		int op;
		scanf("%d",&op);
		if(op==1)
		{
			int x;
			scanf("%d",&x);
			change(1,dfn1[x],dfn2[x]);
		}
		else if(op==2)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			change2(dfn1[x],y);
			change2(dfn2[x],y);
		}
		else
		{
			int x;
			scanf("%d",&x);
			printf("%lld\n",ask(1,dfn1[x],dfn2[x])/2);
		}
	}
	return 0;
}