```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;
int read(){
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;
}
const int N = 1e5+5;
int inf = 1e9;
struct Matrix{
int val[3][3];int h,l;//h行数,l列数
void print(){
for(int i=0;i<h;i++){
for(int j=0;j<l;j++){
cout<<val[i][j]<<" ";
}
cout<<"\n";
}
}
void clear(){
for(int i=0;i<h;i++){
for(int j=0;j<l;j++){
val[i][j] = -inf;
}
}
}
void init(int x){
h = 3;l = 3;
int numm[3][3] =
{ 0,-inf,-inf,
x,x,-inf,
x,x,0
};
for(int i=0;i<h;i++){
for(int j=0;j<l;j++){
val[i][j] = numm[i][j];
}
}
}
void dwy(){
h = 3;l = 3;
int numm[3][3] = {
0,-inf,-inf,
-inf,0,-inf,
-inf,-inf,0
};
for(int i=0;i<h;i++){
for(int j=0;j<l;j++){
val[i][j] = numm[i][j];
}
}
}
};
Matrix cheng(Matrix a,Matrix b){
Matrix res;
res.h = a.h;
res.l = b.l;
res.clear();
for(int i=0;i<a.h;i++){
for(int j=0;j<b.l;j++){
for(int k=0;k<a.l;k++){
res.val[i][j]=max(res.val[i][j],(a.val[i][k]+b.val[k][j]));
}
}
}
return res;
}
Matrix ksm(Matrix x,int k){
Matrix res;
res.dwy();
while(k){
if(k&1){
res = cheng(res,x);
}
x = cheng(x,x);
k>>=1;
}
return res;
}
Matrix Mar(int x,int y){
Matrix res;
int numm[3][3] = {
0,-inf,-inf,
x>=0?y*x:x,y*x,-inf,
x>=0?y*x:x,x>=0?y*x:x,0
};
res.h = 3;
res.l = 3;
for(int i=0;i<res.h;i++){
for(int j=0;j<res.l;j++){
res.val[i][j] = numm[i][j];
}
}
return res;
}
struct aa{
int nxt,to;
}edge[N*2];
int head[N],tote;
void add(int u,int v){
edge[++tote].nxt = head[u];edge[tote].to = v;head[u] = tote;
}
int dep[N],fa[N],top[N],siz[N],son[N],id[N],zh[N],zhi[N];
void dfs1(int u,int f){
siz[u] = 1;
for(int i=head[u];i;i=edge[i].nxt){
int now = edge[i].to;
if(now==f){
continue;
}
fa[now] = u;
dep[now] = dep[u]+1;
dfs1(now,u);
siz[u]+=siz[now];
if(siz[now]>siz[son[u]]){
son[u] = now;
}
}
}
int cnt;
void dfs2(int u,int t){
id[u] = ++cnt;
top[u] = t;
zh[cnt] = zhi[u];
if(!son[u]){
return;
}
dfs2(son[u],t);
for(int i=head[u];i;i=edge[i].nxt){
int now = edge[i].to;
if(now==fa[u]||now==son[u]){
continue;
}
dfs2(now,now);
}
}
int tot=1;
struct nd{
int lc,rc,tag;
Matrix num1,num2;//从左往右，从右往左
}node[N*2];
void pushup(int u){
node[u].num1 = cheng(node[node[u].lc].num1,node[node[u].rc].num1);
node[u].num2 = cheng(node[node[u].rc].num2,node[node[u].lc].num2);
}
void build(int u,int l,int r){
node[u].tag = inf;
if(l==r){
node[u].num1.init(zh[l]);
node[u].num2.init(zh[l]);
return;
}
int mid = (l+r)/2;
node[u].lc = ++tot;
build(tot,l,mid);
node[u].rc = ++tot;
build(tot,mid+1,r);
pushup(u);
}
void lazy_tag(int u,int l,int r,int x){
// Matrix res;res.init(x);
// node[u].num1 = ksm(res,r-l+1);
// node[u].num2 = node[u].num1;
node[u].num1 = Mar(x,r-l+1);
node[u].num2 = Mar(x,r-l+1);
node[u].tag = x;
}
void pushdown(int u,int l,int r){
int mid = (l+r)/2;
lazy_tag(node[u].lc,l,mid,node[u].tag);
lazy_tag(node[u].rc,mid+1,r,node[u].tag);
node[u].tag = inf;
}
void upd(int u,int l,int r,int ll,int rr,int x){
if(l==ll&&r==rr){
lazy_tag(u,l,r,x);
return;
}
if(node[u].tag!=inf){
pushdown(u,l,r);
}
int mid = (l+r)/2;
if(rr<=mid){
upd(node[u].lc,l,mid,ll,rr,x);
}else if(ll>mid){
upd(node[u].rc,mid+1,r,ll,rr,x);
}else{
upd(node[u].lc,l,mid,ll,mid,x);
upd(node[u].rc,mid+1,r,mid+1,rr,x);
}
pushup(u);
}
void query(int u,int l,int r,int ll,int rr,bool fx,Matrix &res){
if(ll<=l&&r<=rr){
if(fx==0){
res = cheng(node[u].num1,res);
return;
}else{
res = cheng(res,node[u].num2);
return;
}
}
if(node[u].tag!=inf){
pushdown(u,l,r);
}
int mid = (l+r)/2;
if(rr>mid){
query(node[u].rc,mid+1,r,ll,rr,fx,res);
}
if(ll<=mid){
query(node[u].lc,l,mid,ll,rr,fx,res);
}
}
int n,m;
void qupd(int u,int v,int x){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]){
swap(u,v);
}
upd(1,1,n,id[top[u]],id[u],x);
u = fa[top[u]];
}
if(dep[u]<dep[v]){
swap(u,v);
}
upd(1,1,n,id[v],id[u],x);
}
int ask(int u,int v){
Matrix res1,res2,res;
res1.dwy();
res2.dwy();
while(top[u]!=top[v]){
if(dep[top[u]]>=dep[top[v]]){
query(1,1,n,id[top[u]],id[u],1,res1);
u = fa[top[u]];
}else{
query(1,1,n,id[top[v]],id[v],0,res2);
}
}
if(dep[u]>=dep[v]){
query(1,1,n,id[v],id[u],1,res1);
}else{
query(1,1,n,id[u],id[v],0,res2);
}
res.h = 3;
res.l = 3;
res.clear();
res.val[0][2] = 0;
res = cheng(res,res1);
res = cheng(res,res2);
return max(0,res.val[0][0]);
}
int main(){
n = read();
for(int i=1;i<=n;i++){
zhi[i] = read();
}
int u,v;
for(int i=1;i<n;i++){
u = read();v = read();
add(u,v);add(v,u);
}
dfs1(1,1);
dfs2(1,1);
build(1,1,n);
m = read();
int k,opt;
while(m--){
opt = read();u = read();v = read();
if(opt==1){
cout<<ask(u,v)<<"\n";
}else{
k = read();
qupd(u,v,k);
}
}
return 0;
}
/*
5
2 2 2 2 3
1 2
2 3
1 4
4 5
1
1 2 5
*/
```
by yizhiming @ 2022-11-07 09:38:15
@[yizhiming](/user/369399) 不用弄从右往左的，可以用类似于 `cheng(a,b)` `cheng(b,a)` 的东西
by _•́へ•́╬_ @ 2022-11-07 10:03:13
@[_•́へ•́╬_](/user/90693) 可是维护区间的时候不得维护这两种的区间积咩？
by yizhiming @ 2022-11-07 10:07:03
哦对了，忘记说了我是 TLE
by yizhiming @ 2022-11-07 10:07:17
@[yizhiming](/user/369399) 我的意思是，不用维护这两种，一种就行了，然后树剖的时候，左边`ans=ans*query`，右边`ans=query*ans`的样子
by _•́へ•́╬_ @ 2022-11-07 10:10:07
@[_•́へ•́╬_](/user/90693) 可是这样的话 query 内部的运算顺序只有一个方向吧？运算顺序不是会影响答案吗。这道题的矩乘不满足交换律吧
by yizhiming @ 2022-11-07 10:14:29
@[yizhiming](/user/369399) 不满足交换律。但是这没问题。
by _•́へ•́╬_ @ 2022-11-07 10:23:06
@[_•́へ•́╬_](/user/90693) 行吧我试试
by yizhiming @ 2022-11-07 10:24:02
@[_•́へ•́╬_](/user/90693) ?哈，为啥要更新 siz[now]？
by yizhiming @ 2022-11-07 10:36:50
还有我改成只维护 num1 还是 TLE。。。
by yizhiming @ 2022-11-07 10:37:43