【题目分析】
问题放到了树上，直接链剖+线段树搞一搞。
调了300行+。
（还是码力不够）
【代码】
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib> #include <map>
#include <set>
#include <queue>
#include <string>
#include <iostream>
#include <algorithm> using namespace std; #define maxn 1000005
#define eps 1e-8
#define db double
#define ll long long
#define inf 0x3f3f3f3f
#define F(i,j,k) for (int i=j;i<=k;++i)
#define D(i,j,k) for (int i=j;i>=k;--i) void Finout()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("wa.txt","w",stdout);
#endif
} int Getint()
{
int x=0,f=1; char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-1; ch=getchar();}
while (ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
return x*f;
} struct Node{
int lx,rx,mx,sum,lazy;
Node operator + (Node x)
{
Node ret;
ret.lx=max(lx,sum+x.lx);
ret.rx=max(x.sum+rx,x.rx);
ret.sum=sum+x.sum;
ret.mx=max(max(mx,x.mx),max(rx+x.lx,max(ret.lx,ret.rx)));
ret.lazy=-inf;
return ret;
}
void print()
{
printf("lx %d rx %d sum %d mx %d lazy %d\n",lx,rx,sum,mx,lazy);
}
void init(){lx=rx=mx=sum=0;lazy=-inf;}
}t[maxn]; int n,a[maxn],b[maxn],q,L,R,tot,x,y,c;
int h[maxn],to[maxn],ne[maxn],en=0;
int fa[maxn],top[maxn],dep[maxn],siz[maxn],pos[maxn],son[maxn]; void add(int a,int b)
{
to[en]=b; ne[en]=h[a]; h[a]=en++;
to[en]=a; ne[en]=h[b]; h[b]=en++;
} void build(int o,int l,int r)
{
if (l==r)
{
t[o].lx=t[o].rx=t[o].mx=t[o].sum=a[l];
t[o].lazy=-inf;
return ;
}
int mid=l+r>>1;
build(o<<1,l,mid);
build(o<<1|1,mid+1,r);
t[o]=t[o<<1]+t[o<<1|1];
t[o].lazy=-inf;
} void dfs1(int o)
{
siz[o]=1;
for (int i=h[o];i>=0;i=ne[i])
{
if (to[i]!=fa[o])
{
fa[to[i]]=o;
dep[to[i]]=dep[o]+1;
dfs1(to[i]);
siz[o]+=siz[to[i]];
if (siz[to[i]]>siz[son[o]]) son[o]=to[i];
}
}
} void dfs2(int o,int tp)
{
top[o]=tp;
pos[o]=++tot;
a[tot]=b[o];
if (!son[o]) return ;
dfs2(son[o],tp);
for (int i=h[o];i>=0;i=ne[i])
if ((to[i]!=fa[o])&&(to[i]!=son[o]))
dfs2(to[i],to[i]);
return ;
} Node q1[maxn],q2[maxn]; void cov(int o,int c,int l,int r)
{
// printf("Node %d %d %d %d\n",o,c,l,r);
t[o].lx=c<0?c:(r-l+1)*c; //printf("%d %d\n",c,(l-r+1)*c);
t[o].rx=c<0?c:(r-l+1)*c;
t[o].sum=(r-l+1)*c;
t[o].mx=c<0?c:(r-l+1)*c;
// printf("lx:%d rx:%d sum:%d mx:%d\n",t[o].lx,t[o].rx,t[o].sum,t[o].mx);
} void pushdown(int o,int l,int r)
{
int mid=l+r>>1;
if (t[o].lazy!=-inf)
{
// printf("pushdown %d\n",o);
// printf("in %d\n",t[o].lazy);
t[o<<1].lazy=t[o<<1|1].lazy=t[o].lazy;
cov(o<<1,t[o].lazy,l,mid);
cov(o<<1|1,t[o].lazy,mid+1,r);
}
t[o].lazy=-inf;
} Node Query(int o,int l,int r)
{
// printf("q down\n");
pushdown(o,l,r);
// printf("Query %d %d\n",l,r);
if (L<=l&&r<=R) return t[o];
int mid=l+r>>1;
if (L>mid) return Query(o<<1|1,mid+1,r);
else if (R<=mid) return Query(o<<1,l,mid);
else return Query(o<<1,l,mid)+Query(o<<1|1,mid+1,r);
} void query()
{
x=Getint(); y=Getint();
// printf("Query %d to %d\n",x,y);
int p1=0,p2=0;
while (top[x]!=top[y])
{
if (dep[top[x]]>dep[top[y]])
{
L=pos[top[x]]; R=pos[x];
q1[++p1]=Query(1,1,n);
// printf("Query %d %d\n",L,R);
// printf("at q1\n"); q1[p1].print();
// printf("x: %d to %d\n",x,fa[top[x]]);
x=fa[top[x]];
}
else
{
L=pos[top[y]]; R=pos[y];
// printf("%d %d\n",L,R);
q2[++p2]=Query(1,1,n);
// printf("Query %d %d\n",L,R);
// printf("at q2\n"); q2[p2].print();
// printf("y: %d to %d\n",y,fa[top[y]]);
y=fa[top[y]];
}
}
if (dep[x]>=dep[y])
{
L=pos[y]; R=pos[x];
// printf("%d %d\n",L,R);
q1[++p1]=Query(1,1,n);
// printf("Query %d %d\n",L,R);
// printf("at q1\n"); q1[p1].print();
}
else
{
L=pos[x]; R=pos[y];
// printf("%d %d\n",L,R);
q2[++p2]=Query(1,1,n);
// printf("Query %d %d\n",L,R);
// printf("at q2\n"); q2[p2].print();
}
/* Node ret1,ret2,ret; ret1.init();ret2.init();ret.init();
printf("q1begin\n");
D(i,p1,1)
{
ret1.print();
ret1=ret1+q1[i];
q1[i].print();
ret1.print();
}
printf("q1 over\n");
ret1.print();
printf("q2 begin\n");
D(i,p2,1)
{
ret2.print();
ret2=ret2+q2[i];
q2[i].print();
ret2.print();
}
printf("q2 over\n");
// ret1.init(); ret2.init();
ret1.print(); ret2.print();
swap(ret2.lx,ret2.rx);
ret=ret1+ret2;
*/
Node ret,ret1,ret2; ret.init(); ret1.init(); ret2.init();
if (!p1)
{
// printf("only p2\n");
ret=q2[1];
F(i,2,p2) ret=q2[i]+ret;
}
else if (!p2)
{
// printf("only p1\n");
ret=q1[1];
F(i,2,p1) ret=q1[i]+ret;
}
else
{
// printf("both p1 and p2\n");
ret1=q1[1];
F(i,2,p1) ret1=q1[i]+ret1;
ret2=q2[1];
F(i,2,p2) ret2=q2[i]+ret2;
swap(ret2.lx,ret2.rx);
ret=ret2+ret1;
}
printf("%d\n",max(ret.mx,0));
} void mod(int o,int l,int r)
{
// printf("mod %d %d %d\n",o,l,r);
pushdown(o,l,r);
int mid=l+r>>1;
if (L<=l&&r<=R)
{
// printf("tag on %d by %d %d to %d\n",o,c,l,r);
t[o].lazy=c;
cov(o,c,l,r);
return ;
}
if (L<=mid) mod(o<<1,l,mid);
if (R>mid) mod(o<<1|1,mid+1,r);
t[o]=t[o<<1]+t[o<<1|1];
} void Modify()
{
x=Getint(); y=Getint(); c=Getint();
while (top[x]!=top[y])
{
if (dep[top[x]]<dep[top[y]]) swap(x,y);
L=pos[top[x]]; R=pos[x];
// printf("modify %d %d %d\n",L,R,c);
mod(1,1,n);
x=fa[top[x]];
}
if (dep[x]<dep[y]) swap(x,y);
L=pos[y]; R=pos[x];
// printf("modify %d %d %d\n",L,R,c);
mod(1,1,n);
} int main()
{
memset(h,-1,sizeof h);
Finout(); n=Getint();
F(i,1,n) b[i]=Getint();
F(i,1,n-1) add(Getint(),Getint());
dfs1(1); dep[0]=-1;
dfs2(1,1);
// F(i,1,n) printf("Node %d : fa %d pos %d dep %d\n",i,fa[i],pos[i],dep[i]);
build(1,1,n);
q=Getint();
F(i,1,q)
{
int opt=Getint();
switch(opt)
{
case 1: query(); break;
case 2: Modify(); break;
}
}
}