。。。。。。。好长啊。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxv 50050
#define maxe 100500
#define inf 2000000000
using namespace std;
int n,m,val[maxv],x,y,z,g[maxv],nume=,fath[maxv],top[maxv],w[maxv],fw[maxv],son[maxv],size[maxv],dis[maxv],times=;
int tot=,root,ls[maxv<<],rs[maxv<<],mn[maxv<<],mx[maxv<<],fr[maxv<<],ba[maxv<<],lazy[maxv<<];
int r1,r2,r3;
struct edge
{
int v,nxt;
}e[maxe];
int read()
{
char ch;int data=;
while (ch<'' || ch>'') ch=getchar();
while (ch>='' && ch<='')
{
data=data*+ch-'';
ch=getchar();
}
return data;
}
void addedge(int u,int v)
{
e[++nume].v=v;
e[nume].nxt=g[u];
g[u]=nume;
}
void dfs1(int x)
{
size[x]=;son[x]=;
for (int i=g[x];i;i=e[i].nxt)
{
int v=e[i].v;
if (v!=fath[x])
{
fath[v]=x;dis[v]=dis[x]+;
dfs1(v);
size[x]+=size[v];
if (size[son[x]]<size[v]) son[x]=v;
}
}
}
void dfs2(int x,int father)
{
w[x]=++times;fw[times]=x;top[x]=father;
if (son[x]) dfs2(son[x],father);
for (int i=g[x];i;i=e[i].nxt)
{
int v=e[i].v;
if ((v!=fath[x]) && (v!=son[x]))
dfs2(v,v);
}
}
void reset()
{
r1=inf;r2=;r3=;
}
void pushup(int now)
{
mx[now]=max(mx[ls[now]],mx[rs[now]]);
mn[now]=min(mn[ls[now]],mn[rs[now]]);
fr[now]=max((mx[rs[now]]-mn[ls[now]]),max(fr[ls[now]],fr[rs[now]]));
ba[now]=max((mx[ls[now]]-mn[rs[now]]),max(ba[ls[now]],ba[rs[now]]));
}
void pushdown(int now,int left,int right)
{
if (!lazy[now]) return;
lazy[ls[now]]+=lazy[now];lazy[rs[now]]+=lazy[now];
mx[ls[now]]+=lazy[now];mx[rs[now]]+=lazy[now];
mn[ls[now]]+=lazy[now];mn[rs[now]]+=lazy[now];
lazy[now]=;
}
void build(int &now,int left,int right)
{
now=++tot;
if (left==right) {mn[now]=mx[now]=val[fw[left]];fr[now]=ba[now]=;return;}
int mid=(left+right)>>;
build(ls[now],left,mid);
build(rs[now],mid+,right);
pushup(now);
}
void ask(int now,int left,int right,int l,int r,int type)
{
pushdown(now,left,right);
if ((left==l) && (right==r))
{
if (type==) r3=max(r3,mx[now]-r1);else r3=max(r3,r2-mn[now]);
if (type==) r3=max(r3,fr[now]);else r3=max(r3,ba[now]);
r1=min(r1,mn[now]);r2=max(r2,mx[now]);
return;
}
int mid=(left+right)>>;
if (r<=mid) ask(ls[now],left,mid,l,r,type);
else if (l>=mid+) ask(rs[now],mid+,right,l,r,type);
else
{
ask(ls[now],left,mid,l,mid,type);
ask(rs[now],mid+,right,mid+,r,type);
}
}
void modify(int now,int left,int right,int l,int r,int x)
{
pushdown(now,left,right);
if ((left==l) && (right==r))
{
lazy[now]+=x;mn[now]+=x;mx[now]+=x;
return;
}
int mid=(left+right)>>;
if (r<=mid) modify(ls[now],left,mid,l,r,x);
else if (l>=mid+) modify(rs[now],mid+,right,l,r,x);
else
{
modify(ls[now],left,mid,l,mid,x);
modify(rs[now],mid+,right,mid+,r,x);
}
pushup(now);
}
int lca(int x,int y)
{
int f1=top[x],f2=top[y];
while (f1!=f2)
{
if (dis[f1]<dis[f2]) {swap(f1,f2);swap(x,y);}
x=fath[f1];f1=top[x];
}
if (dis[x]<dis[y]) return x;else return y;
}
void find_answer(int x,int y,int z)
{
int ans=,t=lca(x,y),mn,mx;
int f1=top[x],f2=top[y];
mn=inf;mx=;
while (f1!=top[t])
{
reset();ask(root,,n,w[f1],w[x],);
ans=max(ans,r2-mn);ans=max(ans,r3);mn=min(mn,r1);
x=fath[f1];f1=top[x];
}
reset();ask(root,,n,w[t],w[x],);
ans=max(ans,r2-mn);ans=max(ans,r3);mn=min(mn,r1);
while (f2!=top[t])
{
reset();ask(root,,n,w[f2],w[y],);
ans=max(ans,mx-r1);ans=max(ans,r3);mx=max(mx,r2);
y=fath[f2];f2=top[y];
}
reset();ask(root,,n,w[t],w[y],);
ans=max(ans,mx-r1);ans=max(ans,r3);mx=max(mx,r2);
ans=max(ans,mx-mn);
printf("%d\n",ans);
}
void modify_tree(int x,int y,int z)
{
int f1=top[x],f2=top[y];
while (f1!=f2)
{
if (dis[f1]<dis[f2]) {swap(f1,f2);swap(x,y);}
modify(root,,n,w[f1],w[x],z);
x=fath[f1];f1=top[x];
}
if (dis[x]>dis[y]) swap(x,y);
modify(root,,n,w[x],w[y],z);
}
int main()
{
n=read();
for (int i=;i<=n;i++) val[i]=read();
for (int i=;i<=n-;i++)
{
x=read();y=read();
addedge(x,y);addedge(y,x);
}
dfs1();
dfs2(,);
build(root,,n);
m=read();
for (int i=;i<=m;i++)
{
x=read();y=read();z=read();
find_answer(x,y,z);
modify_tree(x,y,z);
}
return ;
}