过样例全WA

记录

#include<iostream>
#include<cmath>
#include<string>
#include<string.h>
#include<algorithm>
#define int long long

using namespace std;

const int N=1e5+5;

int n,m;
int answer;
int w[N];
int cnt;
int fa[N],dep[N],size[N],son[N],top[N],id[N],wt[N];
/*
fa[u]:u在树中的父亲
dep[u]:u节点的深度
size[u]:u的子树节点数(子树大小)
son[u]:u的重儿子
top[u]:u所在重链的顶部节点
id[x]:新的编号
wt[y]:新编号的点权 
*/

struct edge
{
	int u,v;
}e[N*2];
int h[N*2],tot;

int sum[N*4],lazy[N*4];

void add(int u,int v)
{
	e[++tot].v=v;
	e[tot].u=h[u];
	h[u]=tot;
}

void dfs1(int u,int f,int deep)
{
	dep[u]=deep;
	fa[u]=f;
	size[u]=1;
	int maxson=-1;
	for(int i=h[u];i!=-1;i=e[i].u)
	{
		int v=e[i].v;
		if(v==f)
			continue;
		dfs1(v,u,deep+1);
		size[u]+=size[v];
		if(size[v]>maxson)
		{
			son[u]=v;
			maxson=size[v];
		}
	}
}

void dfs2(int u,int topf)
{
	id[u]=++cnt;
	wt[cnt]=w[u];
	top[u]=topf;
	if(!son[u])
		return ;
	dfs2(son[u],topf);
	for(int i=h[u];i!=-1;i=e[i].u)
	{
		int v=e[i].v;
		if(v==fa[u] or v==son[u])
			continue;
		dfs2(v,v);
	}
}

void push_up(int u)
{
	sum[u]=sum[2*u]+sum[2*u+1];
}

void push_down(int u,int l,int r)
{
	int mid=(l+r)/2;
	lazy[2*u]+=lazy[u];
	lazy[2*u+1]+=lazy[u];
	sum[2*u]+=lazy[u]*(mid-l+1);
	sum[2*u+1]+=lazy[u]*(r-(mid+1)+1);
	lazy[u]=0;
}

void build(int u,int l,int r)
{
	lazy[u]=0;
	if(l==r)
	{
		sum[u]=wt[l];
		return ;
	}
	int mid=(l+r)/2;
	build(2*u,l,mid);
	build(2*u+1,mid+1,r);
	push_up(u);
}

void update(int L,int R,int c,int l,int r,int u)
{
	if(L<=l&&R>=r)
	{
		lazy[u]+=c;
		sum[u]+=c*(r-l+1);
		return ;
	}
	if(lazy[u])
		push_down(u,l,r);
	int mid=(l+r)/2;
	if(L<=mid)
		update(L,R,c,l,mid,2*u);
	if(R>mid)
		update(L,R,c,mid+1,r,2*u+1);
	push_up(u);
}

void upson(int x,int k)
{
	update(id[x],id[x]+size[x]-1,k,1,n,1);
}

void query(int L,int R,int l,int r,int u)
{
	if(L<=l&&R>=r)
	{
		answer+=sum[u];
		return ;
	}
	if(lazy[u])
		push_down(u,l,r);
	int mid=(l+r)/2;
	if(L<=mid)
		query(L,R,l,mid,2*u);
	if(R>mid)
		query(L,R,mid+1,r,2*u+1);
}

int qrange(int x,int y)
{
	int ans=0;
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])
			swap(x,y);
		answer=0;
		query(id[top[x]],id[x],1,n,1);
		ans+=answer;
		x=fa[top[x]];
	}
	if(dep[x]>dep[y])
		swap(x,y);
	answer=0;
	query(id[x],id[y],1,n,1);
	ans+=answer;
	return ans;
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	memset(h,-1,sizeof h);
	for(int i=1;i<=n;i++)
		cin>>w[i];
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		add(u,v);
		add(v,u);
	}
	dfs1(1,0,1);
	dfs2(1,1);
	build(1,1,n);
	while(m--)
	{
		int op,x,a;
		cin>>op;
		if(op==1)
		{
			cin>>x>>a;
			update(x,x,a,1,n,1);
		}
		else if(op==2)
		{
			cin>>x>>a;
			upson(x,a);
		}
		else if(op==3)
		{
			cin>>x;
			cout<<qrange(1,x)<<endl;
		}
	}
	return 0;
}