C++(clang++11) 解法, 执行用时: 165ms, 内存消耗: 12176K, 提交时间: 2021-04-24 17:51:44

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e4+5;
int p[N];
vector<int>G[N];
int sz[N],dep[N],son[N],f[N];
void dfs(int u,int fa)
{
	sz[u]=1;dep[u]=dep[fa]+1;f[u]=fa;
	for(int v:G[u])
	{
		if(v==fa)	continue;
		dfs(v,u);
		sz[u]+=sz[v];
		if(sz[son[u]]<sz[v])	son[u]=v;
	}
}

int top[N],idx[N],id,val[N];
void DFS(int u,int tp)
{
	idx[u]=++id;
	top[u]=tp;
	val[id]=p[u];
	if(!son[u])	return;
	DFS(son[u],tp);
	for(int v:G[u])
	{
		if(!idx[v])
		{
			DFS(v,v);
		}
	}
}

struct SegTree{
	int l,r,mi,mx,lmx,rmx,lz;
	SegTree	()	{l=r=mx=mi=lz=0;lmx=rmx=0;}
}Tr[N<<2];

void pushup(int u)
{
	Tr[u].mx=max(Tr[u<<1].mx,Tr[u<<1|1].mx);
	Tr[u].mi=min(Tr[u<<1].mi,Tr[u<<1|1].mi);
	Tr[u].lmx=max(Tr[u<<1].mx-Tr[u<<1|1].mi,max(Tr[u<<1].lmx,Tr[u<<1|1].lmx));
	Tr[u].rmx=max(Tr[u<<1|1].mx-Tr[u<<1].mi,max(Tr[u<<1].rmx,Tr[u<<1|1].rmx));
}

void pushdown(int u)
{
	if(Tr[u].lz)
	{
		Tr[u<<1].mx+=Tr[u].lz;
		Tr[u<<1|1].mx+=Tr[u].lz;
		Tr[u<<1].mi+=Tr[u].lz;
		Tr[u<<1|1].mi+=Tr[u].lz;
		Tr[u<<1].lz+=Tr[u].lz;
		Tr[u<<1|1].lz+=Tr[u].lz;
		Tr[u].lz=0;
	}
}

void build(int u,int l,int r)
{
	Tr[u].l=l,Tr[u].r=r;
	if(l==r)
	{
		Tr[u].mx=Tr[u].mi=val[l	];
		return;
	}
	int mid=(l+r)>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	pushup(u);
}

void update(int u,int L,int R,int k)
{
	if(L>Tr[u].r||R<Tr[u].l)	return;
	if(L<=Tr[u].l&&R>=Tr[u].r)
	{
		Tr[u].mx+=k;
		Tr[u].mi+=k;
		Tr[u].lz+=k;
		return;
	}
	pushdown(u);
	update(u<<1,L,R,k);
	update(u<<1|1,L,R,k);
	pushup(u);
}

SegTree merge(SegTree l,SegTree r)
{
	SegTree res;
	res.mx=max(l.mx,r.mx);
	res.mi=min(l.mi,r.mi);
	res.lmx=max(l.mx-r.mi,max(l.lmx,r.lmx));
	res.rmx=max(r.mx-l.mi,max(l.rmx,r.rmx));
	return res;
}

SegTree query(int u,int L,int R)
{
	if(L<=Tr[u].l&&Tr[u].r<=R)	return Tr[u];
	pushdown(u);
	int mid=(Tr[u].r+Tr[u].l)>>1;
	if(R<=mid)	return query(u<<1,L,R);
	if(L>mid)	return query(u<<1|1,L,R);
	return merge(query(u<<1,L,R),query(u<<1|1,L,R));
}

void Treeupdate(int u,int v,int k)
{
	while(top[u]!=top[v])
	{
		if(dep[top[u]]<dep[top[v]])	swap(u,v);
		update(1,idx[top[u]],idx[u],k);
		u=f[top[u]];
	}
	if(dep[u]<dep[v])	swap(u,v);
	update(1,idx[v],idx[u],k);
}

int Treequery(int u,int v)
{
	SegTree x,y;//x维护左 y维护右
	x.mi=y.mi=2e9;
	while(top[u]!=top[v])
	{
		if(dep[top[u]]<dep[top[v]])
		{
			x=merge(query(1,idx[top[v]],idx[v]),x);
			v=f[top[v]];
		}
		else
		{
			y=merge(query(1,idx[top[u]],idx[u]),y); 
			u=f[top[u]];
		}
	}
	if(dep[u]<dep[v])	x=merge(query(1,idx[u],idx[v]),x);
	else				y=merge(query(1,idx[v],idx[u]),y);
	swap(y.rmx,y.lmx);
	return merge(y,x).rmx;
}

int main()
{
  	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&p[i]);
	for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1,1);
	DFS(1,1);
	build(1,1,n);
	int Q;
	scanf("%d",&Q);
	while(Q--)
	{
		int a,b,v;
		scanf("%d%d%d",&a,&b,&v);
		printf("%d\n",Treequery(a,b));
		Treeupdate(a,b,v);
	}
	return 0;
}
/*
3
1 2 3
1 3
2 3
2
1 2 100
1 3 100
*/