记录编号	585475	评测结果	AAAAAAAAA
题目名称	[TJOI 2015] 旅游	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.777 s
提交时间	2023-12-11 21:47:02	内存使用	12.05 MiB

#include <bits/stdc++.h> 
using namespace std;
#define ll long long
const int N = 5e4+10; 
int n,m; 
struct made{
    int ver,nx;
}e[N<<1];
int hd[N],tot,cnt;
int fa[N],size[N],dep[N],son[N];
int a[N],dfn[N],rnk[N],top[N];
struct Tree{
    int l,r,ls,rs,la,ma,mi;
    #define l(x) t[x].l
    #define r(x) t[x].r
    #define la(x) t[x].la
    #define ls(x) t[x].ls
    #define rs(x) t[x].rs
    #define ma(x) t[x].ma
    #define mi(x) t[x].mi
}t[N<<2];
void pushup(int x) {
    ma(x) = max(ma(x<<1),ma(x<<1|1));
    mi(x) = min(mi(x<<1),mi(x<<1|1));
    ls(x) = max(ls(x<<1),max(ls(x<<1|1),ma(x<<1|1)-mi(x<<1)));
    rs(x) = max(rs(x<<1),max(rs(x<<1|1),ma(x<<1)-mi(x<<1|1)));
}
Tree merge(Tree x,Tree y){
    Tree ans;
    ans.ma = max(x.ma,y.ma),ans.mi = min(x.mi,y.mi);
    ans.ls = max(max(x.ls,y.ls),y.ma-x.mi);
    ans.rs = max(max(x.rs,y.rs),x.ma-y.mi);
    return ans;
}
void pushdown(int x){
    if(!la(x))return;
    la(x<<1) += la(x),la(x<<1|1) += la(x);
    ma(x<<1) += la(x),ma(x<<1|1) += la(x);
    mi(x<<1) += la(x),mi(x<<1|1) += la(x);
    la(x) = 0;
}
void build(int x,int l,int r){
    l(x) = l,r(x) = r;
    if(l == r){
        mi(x) = ma(x) = a[rnk[l]];
        return;
    }
    int mid = l + r >> 1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    pushup(x);
}
void change(int x,int l,int r,int z) {
    if(l <= l(x) && r(x) <= r){
        la(x) += z;
        ma(x) += z,mi(x) += z;
        return;
    }
    pushdown(x);
    int mid = l(x) + r(x) >> 1;
    if(l <= mid)change(x<<1,l,r,z);
    if(r > mid)change(x<<1|1,l,r,z);
    pushup(x);
}
Tree ask(int x,int l,int r){
    if(l <= l(x) && r(x) <= r)return t[x];
    pushdown(x);
    int mid = l(x) + r(x) >> 1;
    if(r <= mid)return ask(x<<1,l,r);
    else if(l > mid)return ask(x<<1|1,l,r);
    else return merge(ask(x<<1,l,r),ask(x<<1|1,l,r));
} 
//---------------------
void add(int x,int y){
    tot++;
    e[tot].ver = y,e[tot].nx = hd[x],hd[x] = tot;
}
void dfs1(int x){
    size[x] = 1;
    for(int i = hd[x];i;i = e[i].nx){
        int y = e[i].ver;
        if(dep[y])continue;
        dep[y] = dep[x] + 1;
        fa[y] = x;
        dfs1(y);
        size[x] += size[y];
        if(!son[x] || size[y] > size[son[x]])son[x] = y;
    }
}
void dfs2(int x,int t){
    dfn[x] = ++cnt;
    rnk[cnt] = x;
    top[x] = t;
    if(!son[x])return;
    dfs2(son[x],t);
    for(int i = hd[x];i;i = e[i].nx){
        int y = e[i].ver;
        if(y != fa[x] && y != son[x])dfs2(y,y);
    }
}
int cal(int x,int y){
    Tree L,R;
    L.ls = L.rs = L.la = L.ma = 0,L.mi = 2e9;R = L;
    while(top[x] != top[y]){
        if(dep[top[x]] > dep[top[y]]){
            L = merge(ask(1,dfn[top[x]],dfn[x]),L);
            x = fa[top[x]];   
        }
        else{
            R = merge(ask(1,dfn[top[y]],dfn[y]),R);
            y = fa[top[y]];
        }
    }
    if(dep[x] < dep[y])R = merge(ask(1,dfn[x],dfn[y]),R);
    else L = merge(ask(1,dfn[y],dfn[x]),L);
    swap(L.ls,L.rs);
    Tree ans = merge(L,R);
    return ans.ls;
}
void caladd(int x,int y,int z){
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]])swap(x,y);
        change(1,dfn[top[x]],dfn[x],z);
        x = fa[top[x]];
    }
    if(dep[x] > dep[y])swap(x,y);
    change(1,dfn[x],dfn[y],z);
}
int main(){
    freopen("tjoi2015_travel.in","r",stdin);
    freopen("tjoi2015_travel.out","w",stdout);
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)scanf("%d",&a[i]);
    for(int i = 1;i < n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y),add(y,x);
    }
    dep[1] = 1;
    dfs1(1),dfs2(1,1);
    build(1,1,n);
    scanf("%d",&m);
    for(int i = 1;i <= m;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        printf("%d\n",cal(x,y));
        caladd(x,y,z);
    }
    
    return 0;
    
}