树剖板题球条

// 

#include <bits/stdc++.h>

using namespace std;

void init_vars();
void solve(int testcase, ...);

signed main(){
#ifdef files
	freopen(".in", "r", stdin);
	freopen(".out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	solve(1);
#ifdef files
	fclose(stdin); fclose(stdout);
#endif
	return 0;
}

// funcs
int max(int x, int y, int z){
	return max(x, max(y, z));
}
// Vars
int n, q, w[100001], dep[100001], fat[100001], dfn[100001], tp[100001], hv[100001], sz[100001], ww[100001], tot = 0;
// Segment Tree

#define rng(x) (tree[x].r - tree[x].l + 1)

struct node{
	int l, r, lval, rval, val, sum, lazy;
	node(){
		lazy = 0x3f3f3f3f, lval = rval = val = sum = 0;
		l = r = 0;
	}
	node operator+(const node &b) const{
		node c; c.l = l, c.r = b.r;
		c.lval = max(lval, sum + b.lval);
		c.rval = max(b.rval, rval + b.sum);
		c.val = max(val, b.val, lval + b.rval);
		c.sum = sum + b.sum;
		c.lazy = 0x3f3f3f3f;
		return c;
	}
}tree[100001 << 2];

void build(int l, int r, int p){
	if(l == r){
		tree[p].l = tree[p].r = l;
		tree[p].lval = tree[p].rval = tree[p].val = w[l];
		return;
	}
	int mid = (l + r) / 2;
	build(l, mid, p * 2);
	build(mid + 1, r, p * 2 + 1);
	tree[p] = tree[p * 2] + tree[p * 2 + 1];
}
void mark(int p, int x){
	tree[p].lval = tree[p].rval = tree[p].val = max(0, x * rng(p));
	tree[p].sum = x * rng(p);
	tree[p].lazy = x;
}
void tag(int p){
	if(tree[p].lazy != 0x3f3f3f3f){
		mark(p * 2, tree[p].lazy);
		mark(p * 2 + 1, tree[p].lazy);
		tree[p].lazy = 0x3f3f3f3f;
	}
}
void add(int l, int r, int x, int p){
	if(l <= tree[p].l && tree[p].r <= r){
		mark(p, x);
		return;
	}
	tag(p);
	int mid = (tree[p].l + tree[p].r) / 2;
	if(l <= mid) add(l, r, x, p * 2);
	if(mid < r) add(l, r, x, p * 2 + 1);
	tree[p] = tree[p * 2] + tree[p * 2 + 1];
}
node query(int l, int r, int p){
	if(l <= tree[p].l && tree[p].r <= r)
		return tree[p];
	tag(p);
	int mid = (tree[p].l + tree[p].r) / 2;
	if(l <= mid && mid < r)
		return query(l, r, p * 2) + query(l, r, p * 2 + 1);
	else if(l <= mid)
		return query(l, r, p * 2);
	else
		return query(l, r, p * 2 + 1);
}
#undef rng
// Heavy Link Decomposition

vector<int> gv[100001];

inline void add_edge(int u, int v){
	gv[u].push_back(v);
	gv[v].push_back(u);
}
void dfs(int u, int fa){
	int maxv = 0;
	sz[u] = 1, fat[u] = fa;
	for(auto v : gv[u]){
		if(v == fa) continue;
		dep[v] = dep[u] + 1;
		dfs(v, u);
		sz[u] += sz[v];
		if(maxv < sz[v])
			maxv = sz[v], hv[u] = v;
	}
}
void dfs1(int u, int fa, int rt){
	dfn[u] = ++tot, tp[u] = rt;
	if(hv[u])
		dfs1(hv[u], u, rt);
	for(auto v : gv[u]){
		if(v == fa || v == hv[u])
			continue;
		dfs1(v, u, v);
	}
}
// Add-Query Operations

void add(int u, int v, int x){
	while(tp[u] != tp[v]){
		if(dep[tp[u]] > dep[tp[v]])
			add(dfn[tp[u]], dfn[u], x, 1), u = fat[tp[u]];
		else
			add(dfn[tp[v]], dfn[v], x, 1), v = fat[tp[v]];
	}
	add(min(dfn[u], dfn[v]), max(dfn[u], dfn[v]), x, 1);
}
int query(int u, int v){
	node ans, ans1;
	while(tp[u] != tp[v]){
		if(dep[tp[u]] > dep[tp[v]])
			ans = ans + query(dfn[tp[u]], dfn[u], 1), u = fat[tp[u]];
		else
			ans1 = ans1 + query(dfn[tp[v]], dfn[v], 1), v = fat[tp[v]];
	}
	swap(ans1.lval, ans1.rval);
	ans = ans + query(min(dfn[u], dfn[v]), max(dfn[u], dfn[v]), 1);
	return (ans + ans1).val;
}

void init_vars(){
	// type your initiating code...
}

void solve(int testcase, ...){
	init_vars();
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> w[i];
	for(int i = 1; i < n; i++){
		int u, v; cin >> u >> v;
		add_edge(u, v);
	}
	dfs(1, -1), dfs1(1, -1, 1);
	for(int i = 1; i <= n; i++)
		ww[dfn[i]] = w[i];
	for(int i = 1; i <= n; i++)
		w[i] = ww[i];
	build(1, n, 1);
	cin >> q;
	for(int i = 1; i <= q; i++){
		int op, u, v, x;
		cin >> op >> u >> v;
		if(op == 1) cout << query(u, v) << endl;
		else cin >> x, add(u, v, x);
	}
}