bzoj 3999: [TJOI2015]旅游 LCT

#include <bits/stdc++.h>

#define N 50003

#define lson t[x].ch[0]

#define rson t[x].ch[1]

using namespace std;

namespace IO

{

    void setIO(string s)

    {

        string in=s+".in";

        string out=s+".out";

        freopen(in.c_str(),"r",stdin);

        // freopen(out.c_str(),"w",stdout);

    }

};

const int inf=0x3f3f3f3f;

int edges;

int sta[N],hd[N],to[N<<1],nex[N<<1];

struct node

{

    int ch[2],minv,maxv,lmax,rmax,rev,tag,val,f;

}t[N];

void add(int u,int v)

{

    nex[++edges]=hd[u],hd[u]=edges,to[edges]=v;

}

int get(int x)

{

    return t[t[x].f].ch[1]==x;

}

int isrt(int x)

{

    return !(t[t[x].f].ch[0]==x||t[t[x].f].ch[1]==x);

}

void pushup(int x)

{

    t[x].minv=min(min(t[lson].minv,t[rson].minv), t[x].val);

    t[x].maxv=max(max(t[lson].maxv,t[rson].maxv), t[x].val);

    t[x].lmax=max(max(t[lson].lmax,t[rson].lmax),max(t[lson].maxv,t[x].val)-min(t[x].val,t[rson].minv));

    t[x].rmax=max(max(t[lson].rmax,t[rson].rmax),max(t[rson].maxv,t[x].val)-min(t[x].val,t[lson].minv));

}

void marktag(int x,int v)

{

    if(!x) return;

    t[x].tag+=v,t[x].minv+=v,t[x].maxv+=v,t[x].val+=v;

}

void markrev(int x)

{

    if(!x) return;

    swap(t[x].lmax,t[x].rmax),swap(lson,rson),t[x].rev^=1;

}

void pushdown(int x)

{

    if(t[x].tag)

    {

        marktag(lson,t[x].tag),marktag(rson,t[x].tag);

        t[x].tag=0;

    }

    if(t[x].rev)

    {

        markrev(lson),markrev(rson);

        t[x].rev=0;

    }

}

void rotate(int x)

{

    int old=t[x].f,fold=t[old].f,which=get(x);

    if(!isrt(old)) t[fold].ch[t[fold].ch[1]==old]=x;

    t[old].ch[which]=t[x].ch[which^1],t[t[old].ch[which]].f=old;

    t[x].ch[which^1]=old,t[old].f=x,t[x].f=fold;

    pushup(old),pushup(x);

}

void splay(int x)

{

    int v=0,u=x,fa;

    for(sta[++v]=u;!isrt(u);u=t[u].f) sta[++v]=t[u].f;

    for(;v;--v) pushdown(sta[v]);

    for(u=t[u].f;(fa=t[x].f)!=u;rotate(x))

        if(t[fa].f!=u)

            rotate(get(fa)==get(x)?fa:x);

}

void Access(int x)

{

    for(int y=0;x;y=x,x=t[x].f)

        splay(x),rson=y,pushup(x);

}

void makeroot(int x)

{

    Access(x),splay(x),markrev(x);

}

void split(int x,int y)

{

    makeroot(x),Access(y),splay(y);

}

void dfs(int u,int ff)

{

    t[u].f=ff;

    for(int i=hd[u];i;i=nex[i])

        if(to[i]!=ff) dfs(to[i],u);

    pushup(u);

}

int main()

{

    // IO::setIO("input");

    int i,j,n,q;

    t[0].minv=inf,t[0].maxv=-inf;

    scanf("%d",&n);

    for(i=1;i<=n;++i) scanf("%d",&t[i].val);

    for(i=1;i<n;++i)

    {

        int x,y;

        scanf("%d%d",&x,&y),add(x,y),add(y,x);

    }

    dfs(1,0);

    scanf("%d",&q);

    for(i=1;i<=q;++i)

    {

        int a,b,v;

        scanf("%d%d%d",&a,&b,&v);

        split(a,b);

        printf("%d\n",t[b].rmax);

        marktag(b,v);

    }

    return 0;

}