Why does my code WA on the master judge?
#include <iostream>
#define int long long
using namespace std;
const int kMaxN=1e5+1;
struct SPLF
{
int size,deep,heavyson,newid,top,father;
}s[kMaxN*2];
struct XDS
{
int l,r;
int maxl,maxr,maxa,sum,tag;
}tr[kMaxN*4];
struct EDGE
{
int to,nt;
}e[kMaxN*2];
int hd[kMaxN],cnt;
int n,a[kMaxN],b[kMaxN],q,num;
void Pushup(int where)
{
tr[where].maxl=max(tr[where<<1].maxl,tr[where<<1].sum+tr[where<<1|1].maxl);
tr[where].maxr=max(tr[where<<1|1].maxr,tr[where<<1|1].sum+tr[where<<1].maxr);
tr[where].maxa=max(max(tr[where<<1].maxa,tr[where<<1|1].maxa),tr[where<<1].maxr+tr[where<<1|1].maxl);
tr[where].sum=tr[where<<1].sum+tr[where<<1|1].sum;
}
void Build(int where,int l,int r)
{
tr[where].l=l,tr[where].r=r,tr[where].tag=1145141919810;
if(l==r)
{
tr[where].sum=b[l];
tr[where].maxa=tr[where].maxl=tr[where].maxr=max(0ll,b[l]);
return;
}
int mid=(l+r)>>1;
Build(where<<1,l,mid);
Build(where<<1|1,mid+1,r);
Pushup(where);
}
XDS Mixup(XDS i,XDS j)
{
XDS ans;
ans.maxl=max(i.maxl,i.sum+j.maxl);
ans.maxr=max(j.maxr,j.sum+i.maxr);
ans.maxa=max(max(i.maxa,j.maxa),i.maxr+j.maxl);
ans.sum=i.sum+j.sum;
return ans;
}
void Spread(int where)
{
if(tr[where].tag==1145141919810)return;
tr[where<<1].sum=(tr[where<<1].r-tr[where<<1].l+1)*tr[where].tag;
tr[where<<1].maxa=tr[where<<1].maxl=tr[where<<1].maxr=max(tr[where<<1].sum,0ll);
tr[where<<1|1].sum=(tr[where<<1|1].r-tr[where<<1|1].l+1)*tr[where].tag;
tr[where<<1|1].maxa=tr[where<<1|1].maxl=tr[where<<1|1].maxr=max(tr[where<<1|1].sum,0ll);
tr[where<<1].tag=tr[where].tag,tr[where<<1|1].tag=tr[where].tag;
tr[where].tag=1145141919810;
}
XDS GetCut(int where,int l,int r)
{
if(tr[where].l>=l&&tr[where].r<=r)return tr[where];
Spread(where);
int mid=(tr[where].l+tr[where].r)>>1;
XDS ans;
if(mid>=l&&mid<r)ans=Mixup(GetCut(where<<1,l,r),GetCut(where<<1|1,l,r));
else if(mid>=l)ans=GetCut(where<<1,l,r);
else ans=GetCut(where<<1|1,l,r);
Pushup(where);
return ans;
}
void Update(int where,int l,int r,int k)
{
if(tr[where].l>=l&&tr[where].r<=r)
{
tr[where].sum=(tr[where].r-tr[where].l+1)*k;
tr[where].maxa=tr[where].maxl=tr[where].maxr=max(tr[where].sum,0ll);
tr[where].tag=k;
return;
}
Spread(where);
int mid=(tr[where].l+tr[where].r)>>1;
if(mid>=l)Update(where<<1,l,r,k);
if(mid<r)Update(where<<1|1,l,r,k);
Pushup(where);
}
void Add(int x,int y)
{
e[++cnt].to=y;
e[cnt].nt=hd[x];
hd[x]=cnt;
}
void Dfs1(int now,int last)
{
s[now].father=last;
s[now].deep=s[last].deep+1;
s[now].size=1;
int maxa=-1;
for(int i=hd[now];i;i=e[i].nt)
{
if(e[i].to==last)continue;
Dfs1(e[i].to,now);
s[now].size+=s[e[i].to].size;
if(s[e[i].to].size>maxa)
{
s[now].heavyson=e[i].to;
maxa=s[e[i].to].size;
}
}
}
void Dfs2(int now,int top)
{
s[now].top=top;
s[now].newid=++num;
b[num]=a[now];
if(!s[now].heavyson)return;
Dfs2(s[now].heavyson,top);
for(int i=hd[now];i;i=e[i].nt)
{
if(e[i].to==s[now].father||e[i].to==s[now].heavyson)continue;
Dfs2(e[i].to,e[i].to);
}
}
int GetAns(int x,int y)
{
XDS ans;
ans.maxl=ans.maxr=0;
ans.sum=ans.maxa=0;
while(s[x].top!=s[y].top)
{
if(s[s[x].top].deep<s[s[y].top].deep)swap(x,y);
ans=Mixup(ans,GetCut(1,s[s[x].top].newid,s[x].newid));
x=s[s[x].top].father;
}
if(s[x].deep>s[y].deep)swap(x,y);
ans=Mixup(ans,GetCut(1,s[x].newid,s[y].newid));
return ans.maxa;
}
void Change(int x,int y,int k)
{
while(s[x].top!=s[y].top)
{
if(s[s[x].top].deep<s[s[y].top].deep)swap(x,y);
Update(1,s[s[x].top].newid,s[x].newid,k);
x=s[s[x].top].father;
}
if(s[x].deep>s[y].deep)swap(x,y);
Update(1,s[x].newid,s[y].newid,k);
}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
Add(u,v);
Add(v,u);
}
Dfs1(1,0);
Dfs2(1,1);
Build(1,1,n);
cin>>q;
while(q--)
{
int order;
cin>>order;
if(order==1)
{
int a,b;
cin>>a>>b;
cout<<max(GetAns(a,b),(long long)0)<<"\n";
}
else
{
int a,b,c;
cin>>a>>b>>c;
Change(a,b,c);
}
}
return 0;
}