传送门
树链剖分菜题。
题意不清差评。
题意简述（保证清晰）：给一棵带权的树，每次从aaa走到bbb，在走过的路径上任意找两个点，求后访问的点与先访问的点点权差的最大值。
思路：
考虑暴力：维护路径的前缀最小值和后缀最大值然后更新答案。
然后可以用线段树优化这个过程。
对于当前的线段树节点，它的答案=max(左儿子答案，右儿子答案，右儿子最大值−左儿子最小值)max(左儿子答案，右儿子答案，右儿子最大值-左儿子最小值)max(左儿子答案，右儿子答案，右儿子最大值−左儿子最小值)
然后由于路径是有向的，因此在树链剖分两边跳的时候也要考虑方向的因素。
所以还要维护一个跟上面对称的信息，即路径的前缀最大值和后缀最小值。
然后就没了。
代码：
#include<bits/stdc++.h>
#define ri register int
#define lc (p<<1)
#define rc (p<<1|1)
#define mid (T[p].l+T[p].r>>1)
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
typedef long long ll;
const int N=5e4+5;
const ll inf=1e18;
int n,tot=0,a[N],num[N],pred[N],siz[N],hson[N],top[N],dep[N],fa[N];
vector<int>e[N];
struct Node{
int l,r;ll mx,mn,det[2],add;
Node(){l=r=add=0,mx=-inf,mn=inf,det[0]=det[1]=-inf;}
}T[N<<2];
inline Node operator+(const Node&a,const Node&b){
Node ret;
ret.l=a.l,ret.r=b.r,ret.add=0;
ret.mx=max(a.mx,b.mx),ret.mn=min(a.mn,b.mn);
ret.det[0]=max(max(a.det[0],b.det[0]),b.mx-a.mn);
ret.det[1]=max(max(a.det[1],b.det[1]),a.mx-b.mn);
return ret;
}
inline void pushnow(int p,ll v){T[p].mx+=v,T[p].mn+=v,T[p].add+=v;}
inline void pushdown(int p){if(T[p].add)pushnow(lc,T[p].add),pushnow(rc,T[p].add),T[p].add=0;}
inline void build(int p,int l,int r){
T[p].l=l,T[p].r=r;
if(l==r){T[p].mx=T[p].mn=a[pred[l]];return;}
build(lc,l,mid),build(rc,mid+1,r),T[p]=T[lc]+T[rc];
}
inline void update(int p,int ql,int qr,ll v){
if(ql<=T[p].l&&T[p].r<=qr)return pushnow(p,v);
pushdown(p);
if(qr<=mid)update(lc,ql,qr,v);
else if(ql>mid)update(rc,ql,qr,v);
else update(lc,ql,mid,v),update(rc,mid+1,qr,v);
T[p]=T[lc]+T[rc];
}
inline Node query(int p,int ql,int qr){
if(ql<=T[p].l&&T[p].r<=qr)return T[p];
pushdown(p);
if(qr<=mid)return query(lc,ql,qr);
if(ql>mid)return query(rc,ql,qr);
return query(lc,ql,mid)+query(rc,mid+1,qr);
}
inline void change(int x,int y,ll v){
while(top[x]^top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
update(1,num[top[x]],num[x],v),x=fa[top[x]];
}
if(dep[x]<dep[y])swap(x,y);
update(1,num[y],num[x],v);
}
inline int lca(int x,int y){
while(top[x]^top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
x=fa[top[x]];
}
return dep[x]<dep[y]?x:y;
}
inline ll ask(int x,int y){
bool f=x+y==11;
int t=lca(x,y);
Node t1,t2;
while(top[x]^top[t])t1=query(1,num[top[x]],num[x])+t1,x=fa[top[x]];
while(top[y]^top[t])t2=query(1,num[top[y]],num[y])+t2,y=fa[top[y]];
if(y==t)t1=query(1,num[t],num[x])+t1;
else t2=query(1,num[t],num[y])+t2;
return max(max(t1.det[1],t2.det[0]),max(0ll,t2.mx-t1.mn));
}
void bfs(){
static int q[N],hd,tl;
q[hd=tl=1]=1;
while(hd<=tl){
int p=q[hd++];
siz[p]=1;
for(ri i=0,v;i<e[p].size();++i){
if((v=e[p][i])==fa[p])continue;
fa[v]=p,dep[v]=dep[p]+1,q[++tl]=v;
}
}
for(ri i=n,p;i;--i){
p=q[i];
if(i^1){
siz[fa[p]]+=siz[p];
if(siz[p]>siz[hson[fa[p]]])hson[fa[p]]=p;
}
}
q[hd=tl=n]=1;
while(hd<=tl){
int p=q[hd++];
top[p]=hson[fa[p]]==p?top[fa[p]]:p;
pred[num[p]=++tot]=p;
if(!hson[p])continue;
for(ri i=0,v;i<e[p].size();++i){
if((v=e[p][i])==fa[p]||v==hson[p])continue;
q[--hd]=v;
}
q[--hd]=hson[p];
}
}
int main(){
n=read();
for(ri i=1;i<=n;++i)a[i]=read();
for(ri i=1,u,v;i<n;++i)u=read(),v=read(),e[u].push_back(v),e[v].push_back(u);
bfs(),build(1,1,n);
for(ri tt=read(),u,v;tt;--tt){
u=read(),v=read();
ll w=read();
cout<<ask(u,v)<<'\n';
change(u,v,w);
}
return 0;
}