题目大意
对一颗树进行两种操作：将一条从 \(u\) 到 \(v\) 的链上的点的权值增加 \(x\)；查询从 \(u\) 到 \(v\) 的链上最大的 \(p_i-p_j(dis_{ui}<dis_{uj})\)，其中 \(p_i\) 表示点 \(i\) 的权值，\(dis_{AB}\) 表示点 \(A,B\) 间唯一路径上边的数量。
思路分析
先思考，如果没有 \(dis_{ui}<dis_{uj}\) 这个条件，那么这个问题将十分简单，我们只需要用线段树维护链上的最大值，最小值，实现区间加操作即可。
但是多了这个限制条件，我们的做法就要做出一些改变。
首先，我们可以发现，这个条件是有方向性的。也就是说，对于一对查询的 \(u,v\)，如果将 \(u,v\) 交换，查询的结果可能会发生变化，这与我们熟知的链上的和，最大值，最小值之类的是不同的。
那么我们可以先将问题简化，将树上问题变成序列问题。
在序列上维护这样一种带有方向性的可合并的信息，我们最常用的方法就是线段树，而线段树维护的核心就是区间合并，所以我们先思考区间合并如何实现。
容易发现，其实我们只需要维护区间的最大值 \(\text{max}\)，最小值 \(\text{min}\)，从左向右的最大差值 \(\text{atob}\)，从右向左的最大差值 \(\text{btoa}\)（十分形象）就可以解决这个问题，具体的维护方法如下：
a.max=max(ls.max,rs.max);
a.min=min(ls.min,rs.min);
a.atob=max(max(ls.atob,rs.atob),ls.max-rs.min);
a.btoa=max(max(ls.btoa,rs.btoa),rs.max-ls.min);
剩下的线段树部分十分套路，想必大家都会写。（区间加，区间查询某个属性）
那么，我们现在既然有了序列上问题的做法，剩下的就只有把这个做法扩展到树上了。
对于一颗静态树上的链的维护和查询，最常用的方法无疑是树链剖分，树链剖分的思想主要分两个部分，一是把链拆成若干个连续的区间用线段树维护区间信息，二是将所有的区间合并成链，我们既然已经解决了第一个部分，第二个部分的做法就比较显然了。
对于一条链上的查询，如下图：
黑色箭头所指的方向是我们的 \(\text{dfs}\) 序的方向，也就是我们线段树的方向，也就是说，对于线段树而言，图中黑色的 \(l,r\) 是它认为的左边和右边。
但我们实际想要查询的方向是蓝色箭头所指的方向，我们发现，在从 \(u\to \text{LCA}(u,v)\) 的路径上，线段树的方向与我们想要查询的方向南辕北辙，为了解决这个问题，我们在链上的合并时，先从起点和终点分别按照线段树方向维护两个链上的信息，在最后一步时将起点所在链的信息翻转，再与终点链的信息合并，从而得到完整的信息。
这么说可能有点抽象，具体看代码。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=100100;//双向边，不要在乎空间，全部开双倍
int to[N],nxt[N],head[N],w[N];//链星
int top[N],fa[N],dfn[N],rnk[N],siz[N],dep[N],son[N];//树剖七件套
int idx,cnt,n,q,in1,in2,in3;
void add(int u,int v){idx++;to[idx]=v;nxt[idx]=head[u];head[u]=idx;}
void Swap(int &x,int &y){int t=x;x=y;y=t;}
struct STn{int l,r,max,min,atob,btoa,t;};//线段树节点，t是懒标记
void merge(STn &res,STn ls,STn rs){//合并信息
res.max=max(ls.max,rs.max);
res.min=min(ls.min,rs.min);
res.atob=max(max(ls.atob,rs.atob),ls.max-rs.min);
res.btoa=max(max(ls.btoa,rs.btoa),rs.max-ls.min);
}
struct ST{//常规线段树
STn a[N<<2];
void add_t(int p,int k){a[p].t+=k;a[p].max+=k;a[p].min+=k;return ;}//区间加
void push_down(int p){if(a[p].t){add_t(p<<1,a[p].t);add_t(p<<1|1,a[p].t);a[p].t=0;}return ;}//下放懒标记
void build(int p,int l,int r){//常规建树
a[p].l=l;a[p].r=r;a[p].t=0;
if(a[p].l==a[p].r){a[p].min=a[p].max=w[rnk[a[p].l]];a[p].atob=a[p].btoa=0;return ;}//初值
int mid=(a[p].l+a[p].r)>>1;
build(p<<1,l,mid);build(p<<1|1,mid+1,r);
merge(a[p],a[p<<1],a[p<<1|1]);return ;
}
void add(int p,int l,int r,int k){//常规的区间加
if(l<=a[p].l&&a[p].r<=r){add_t(p,k);return ;}
push_down(p);int mid=(a[p].l+a[p].r)>>1;
if(l<=mid) add(p<<1,l,r,k);if(r>mid) add(p<<1|1,l,r,k);
merge(a[p],a[p<<1],a[p<<1|1]);return ;
}
STn ask(int p,int l,int r){//常规的区间查询
if(l<=a[p].l&&a[p].r<=r) return a[p];
push_down(p);int mid=(a[p].l+a[p].r)>>1;
if(r<=mid) return ask(p<<1,l,r);
if(l>mid) return ask(p<<1|1,l,r);
STn res;merge(res,ask(p<<1,l,r),ask(p<<1|1,l,r));
return res;
}
}tree;
void dfs_1(int s,int gr){//常规的树剖dfs1
dep[s]=dep[gr]+1;fa[s]=gr;
son[s]=-1;siz[s]=1;
for(int i=head[s];i;i=nxt[i]){
int v=to[i];
if(v==gr) continue;
dfs_1(v,s);
siz[s]+=siz[v];
if(son[s]==-1||siz[v]>siz[son[s]]) son[s]=v;
}
}
void dfs_2(int s,int tp){//常规的树剖dfs2
top[s]=tp;dfn[s]=++cnt;rnk[cnt]=s;
if(son[s]==-1) return ;
dfs_2(son[s],tp);
for(int i=head[s];i;i=nxt[i]){
int v=to[i];
if(v!=son[s]&&v!=fa[s]) dfs_2(v,v);
}
}
void add_all(int x,int y,int k){//常规的链上加
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) Swap(x,y);
tree.add(1,dfn[top[x]],dfn[x],k);x=fa[top[x]];
}
tree.add(1,min(dfn[x],dfn[y]),max(dfn[x],dfn[y]),k);
}
int query(int x,int y){//不常规的查询
STn l={0,0,-0x3f3f3f3f,0x3f3f3f3f,0,0,0},r=l;//先把两条链的初值赋上
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]){merge(r,tree.ask(1,dfn[top[y]],dfn[y]),r);y=fa[top[y]];}//分起点和终点，不能swap
else{merge(l,tree.ask(1,dfn[top[x]],dfn[x]),l);x=fa[top[x]];}
//注意点：合并时 l,r 应该放在后边作为右区间进行合并
}
if(dep[x]>dep[y]) merge(l,tree.ask(1,dfn[y],dfn[x]),l);
else merge(r,tree.ask(1,dfn[x],dfn[y]),r);//分两种完成最后一次合并
return max(max(l.atob,r.btoa),r.max-l.min);//这里没有把区间翻转，而是直接利用区间信息完成合并
//注意点：如何合并，结合图像理解
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&w[i]);
for(int i=1;i<n;i++){
scanf("%d%d",&in1,&in2);
add(in1,in2);add(in2,in1);
}//常规输入
dfs_1(1,0);dfs_2(1,1);
tree.build(1,1,n);//常规预处理
scanf("%d",&q);
while(q--){
scanf("%d%d%d",&in1,&in2,&in3);
cout<<max(query(in1,in2),0)<<'\n';//肯定不会亏本吧
add_all(in1,in2,in3);//完事之后区间加
}
return 0;
}