蒟蒻求助树剖QAQ

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 100100
#define int long long
int n,m,cnt,tot;
int dep[N],head[N],fa[N],siz[N],tp[N],son[N],dfn[N],rk[N],num[N];
struct Edge{
    int nxt,to;
}edge[N*2];
struct Tree{
    int l,r,lm,rm,maxn,sum,lz;
    bool f;
    Tree(){lm=rm=maxn=sum=lz=f=0;}
}tree[N*4];
void add(int from,int to)
{
    edge[++cnt].nxt=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}
void dfs1(int cur,int pre)
{
    dep[cur]=dep[pre]+1;
    fa[cur]=pre;
    siz[cur]=1;
    for(int i=head[cur];i;i=edge[i].nxt)
    {
        int nxt=edge[i].to;
        if(nxt==pre)continue;
        dfs1(nxt,cur);
        siz[cur]+=siz[nxt];
        if(siz[son[cur]]<siz[nxt])son[cur]=nxt;
    }
}
void dfs2(int cur, int top)
{
    dfn[cur]=++tot;
    rk[tot]=cur;
    tp[cur]=top;
    if(son[cur])dfs2(son[cur],top);
    for(int i=head[cur];i;i=edge[i].nxt)
    {
        int nxt=edge[i].to;
        if(nxt==fa[cur]||nxt==son[cur])continue;
        dfs2(nxt,nxt);
    }
}
Tree merge(Tree L,Tree R)
{
    Tree tmp;
    tmp.l=L.l;tmp.r=R.r;
    tmp.lm=max(L.lm,L.sum+R.lm);
    tmp.rm=max(R.rm,R.sum+L.rm);
    tmp.sum=L.sum+R.sum;
    tmp.maxn=max(max(L.maxn,R.maxn),L.rm+R.lm);
    tmp.lz=tmp.f=0;
    return tmp; 
}
void pushup(int id)
{
    tree[id]=merge(tree[id*2],tree[id*2+1]);
    tree[id].l=tree[id*2].l;tree[id].r=tree[id*2+1].r;
}
void update(int id,int k)
{
    tree[id].f=1;
    tree[id].lz=k;
    tree[id].sum=(tree[id].r-tree[id].l+1)*k;
    tree[id].maxn=tree[id].lm=tree[id].rm=max(tree[id].sum,0ll);
}
void pushdown(int id)
{
    if(!tree[id].f)return;
    update(id*2,tree[id].lz);
    update(id*2+1,tree[id].lz);
    tree[id].f=0;
}
void build(int id,int l,int r)
{
    tree[id].l=l;tree[id].r=r;
    if(l==r)
    {
        tree[id].sum=num[rk[l]];
        tree[id].maxn=tree[id].lm=tree[id].rm=max(tree[id].sum,0ll);
        return;
    }
    int mid=(l+r)/2;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
    tree[id]=merge(tree[id*2],tree[id*2+1]);
}
void make(int id,int l,int r,int k)
{
    if(l<=tree[id].l&&tree[id].r<=r)
    {
        tree[id].lz=k;
        tree[id].f=1;
        tree[id].sum=(tree[id].r-tree[id].l+1)*k;
        return;
    }
    pushdown(id);
    int mid=(tree[id].l+tree[id].r)/2;
    if(l<=mid)make(id*2,l,r,k);
    if(r>mid)make(id*2+1,l,r,k);
    pushup(id);
}
Tree find(int id,int l,int r)
{
    if(l<=tree[id].l&&tree[id].r<=r)return tree[id];
    pushdown(id);
    int mid=(tree[id].l+tree[id].r)/2;
    Tree L,R;
    if(l<=mid)L=find(id*2,l,r);
    if(r>mid)R=find(id*2+1,l,r);
    return merge(L,R);
}
void makef(int x,int y,int k)
{
    while(tp[x]!=tp[y])
    {
        if(dep[tp[x]]<dep[tp[y]])swap(x,y);
        make(1,dfn[tp[x]],dfn[x],k);
        x=tp[x];x=fa[x];
    }
    if(dep[x]<dep[y])swap(x,y);
    make(1,dfn[y],dfn[x],k);
}
//Tree findf(int x,int y)
//{
//  Tree L,R;
//  while(tp[x]!=tp[y])
//  {
//      if(dep[tp[x]]<dep[tp[y]])
//      {
//          L=merge(L,find(1,dfn[tp[y]],dfn[y]));
//          y=tp[y];y=fa[y];
//      }
//      else
//      {
//          R=merge(R,find(1,dfn[tp[x]],dfn[x]));
//          x=tp[x];x=fa[x];
//      }
//  }
//  if(dep[x]<dep[y])L=merge(L,find(1,dfn[x],dfn[y]));
//  else R=merge(R,find(1,dfn[y],dfn[x]));
//  swap(R.lm,R.rm);
//  return merge(L,R);
//}
Tree findf(int x,int y)
{
    Tree L,R;
    while(tp[x]!=tp[y])
    {
        if(dep[tp[x]]>dep[tp[y]])
        {
            L=merge(L,find(1,dfn[tp[x]],dfn[x]));
            x=fa[tp[x]];            
        }
        else
        {
            R=merge(R,find(1,dfn[tp[y]],dfn[y]));
            y=fa[tp[y]];
        }
    }
    if(dep[x]>dep[y])L=merge(L,find(1,dfn[y],dfn[x]));
    else R=merge(R,find(1,dfn[x],dfn[y]));
    swap(L.lm,L.rm);
    return merge(L,R);
}
signed main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;++i)scanf("%lld",&num[i]);
    for(int i=1;i<n;++i)
    {
        int x,y;
        scanf("%lld%lld",&x,&y);
        add(x,y);
        add(y,x);
    }
    dfs1(1,0);
    dfs2(1,1);
    build(1,1,n);
    scanf("%lld",&m);
    for(int i=1;i<=m;++i)
    {
        int k,x,y,z;
        scanf("%lld",&k);
        if(k==1)
        {
            scanf("%lld%lld",&x,&y);
            printf("%lld\n",findf(x,y).maxn);
        }
        else if(k==2)
        {
            scanf("%lld%lld%lld",&x,&y,&z);
            makef(x,y,z);
        }
    }
    return 0;
}