旅游

题目大意

对一颗树进行两种操作：将一条从 $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;
}