线段树 + 树剖...

过了题解里的两组 hack 数据，但是 WA #1。

求求佬们带带QAQ，真的调不动了。或者说给个 hackdata 也行QAQ。

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define maxn 100050
#define maxm 200050 
#define vi vector <int>
#define vvi vector <vi>
#define endl '\n'
#define ll long long
using namespace std;

int n;
struct sgt{
	int sum, pre, suf, mxsum;
	void init(){
		sum = pre = suf = mxsum = 0;
	}
} tree[maxn << 2];
int a[maxn], tag[maxn << 2];

sgt merge_tree(sgt A, sgt B)
{
	sgt tmp; tmp.init();
	tmp.sum = A.sum + B.sum;
	tmp.pre = max(A.pre, A.sum + B.pre);
	tmp.suf = max(B.suf, A.suf + B.sum);
	tmp.mxsum = max({A.mxsum, B.mxsum, A.suf + B.pre});
	return tmp;
}

int ls(int p) {return p << 1;}
int rs(int p) {return p << 1 | 1;}

void push_up(int p)
{
	tree[p] = merge_tree(tree[ls(p)], tree[rs(p)]);
}

void build(int p, int l, int r)
{
	tag[p] = -inf;
	if(l == r){
		tree[p] = {a[l], max(0, a[l]), max(0, a[l]), max(0, a[l])};
		return;
	}
	int mid = (l + r) >> 1;
	build(ls(p), l, mid);
	build(rs(p), mid + 1, r);
	push_up(p);
}

void f(int p, int l, int r, int k)
{
	tag[p] = k;
	int tsum = (r - l + 1) * k;
	tree[p] = {tsum, max(tsum, 0), max(tsum, 0), max(tsum, 0)};
}

void push_down(int p, int l, int r)
{
	int mid = (l + r) >> 1;
	f(ls(p), l, mid, tag[p]);
	f(rs(p), mid + 1, r, tag[p]);
	tag[p] = -inf;
}

void update(int ul, int ur, int p, int l, int r, int k)
{
	if(ul <= l && ur >= r){
		f(p, l, r, k);
		return;
	}
//	if(tag[p] != -inf) push_down(p, l, r); 
//	貌似这里不需要 pushdown，因为直接更新了
	int mid = (l + r) >> 1;
	if(ul <= mid) update(ul, ur, ls(p), l, mid, k);
	if(ur > mid) update(ul, ur, rs(p), mid + 1, r, k);
	push_up(p);
}

sgt query(int ql, int qr, int p, int l, int r)
{
	if(ql <= l && qr >= r){
		return tree[p];
	}
	if(tag[p] != -inf) push_down(p, l, r);
	int mid = (l + r) >> 1;
	sgt tmpl, tmpr, tmp; tmpl.init(), tmpr.init();
	if(ql <= mid) tmpl = query(ql, qr, ls(p), l, mid);
	if(qr > mid) tmpr = query(ql, qr, rs(p), mid + 1, r);
	tmp = merge_tree(tmpl, tmpr);
	return tmp;
}

//--- sgt ---

int head[maxn], nxt[maxm], to[maxm], cnt;
int dep[maxn], fa[maxn], hson[maxn], siz[maxn], tp[maxn];
int dfn[maxn], rdfn[maxn], tim;

void add_edge(int u, int v)
{
	nxt[++ cnt] = head[u];
	head[u] = cnt;
	to[cnt] = v;
}

void dfs1(int x, int ft)
{
	dep[x] = dep[ft] + 1, siz[x] = 1, fa[x] = ft;
	int mxs = 0;
	for(int i = head[x]; i; i = nxt[i]){
		int y = to[i];
		if(y == fa[x]) continue;
		dfs1(y, x);
		siz[x] += siz[y];
		if(mxs < siz[y]){
			mxs = siz[y], hson[x] = y;
		}
	}
}

void dfs2(int x)
{
	dfn[x] = ++ tim;
	if(hson[x]){
		tp[hson[x]] = tp[x];
		dfs2(hson[x]);
	}
	for(int i = head[x]; i; i = nxt[i]){
		int y = to[i];
		if(y == fa[x]) continue;
		if(!tp[y]){
			tp[y] = y;
			dfs2(y);
		}
	}
	rdfn[x] = tim;
}

sgt query_path(int x, int y)
{
	sgt tmp, tmpa, tmpb; tmp.init(), tmpa.init(), tmpb.init();
	while(tp[x] != tp[y]){
		if(dep[tp[x]] > dep[tp[y]]){
			tmpa = merge_tree(tmpa, query(dfn[tp[x]], dfn[x], 1, 1, n));
			x = fa[tp[x]];
		}
		else{
			tmpb = merge_tree(query(dfn[tp[y]], dfn[y], 1, 1, n), tmpb);
			y = fa[tp[y]];
		}
	}
	//x 正拼接，y 反拼接
	if(dep[x] > dep[y]){
		tmp = query(dfn[y], dfn[x], 1, 1, n);
		swap(tmp.suf, tmp.pre); //dep[x] > dep[y] 中间的过渡链要翻转一下。
		tmp = merge_tree(tmpa, tmp);
		tmp = merge_tree(tmp, tmpb);
	}
	else{
		tmp = merge_tree(tmpa, query(dfn[x], dfn[y], 1, 1, n));
		tmp = merge_tree(tmp, tmpb);
	}
	return tmp;
}

void update_path(int x, int y, int k)
{
	while(tp[x] != tp[y]){
		if(dep[tp[x]] > dep[tp[y]]){
			update(dfn[tp[x]], dfn[x], 1, 1, n, k);
			x = fa[tp[x]];
		}
		else{
			update(dfn[tp[y]], dfn[y], 1, 1, n, k);
			y = fa[tp[y]];
		}
	}
	if(dep[x] > dep[y]) update(dfn[y], dfn[x], 1, 1, n, k);
	else update(dfn[x], dfn[y], 1, 1, n, k);
}

int b[maxn];

void solve()
{
	cin >> n;
	for(int i = 1; i <= n; i ++) cin >> b[i];
	for(int i = 1; i < n; i ++){
		int u, v; cin >> u >> v;
		add_edge(u, v); add_edge(v, u);
	}
	dfs1(1, 0);
	tp[1] = 1;
	dfs2(1);
	for(int i = 1; i <= n; i ++) a[dfn[i]] = b[i];
	build(1, 1, n);
	int q; cin >> q;
	for(int i = 1; i <= q; i ++){
		int op; cin >> op;
		if(op == 1){
			int x, y; cin >> x >> y;
			sgt tmp = query_path(x, y);
			cout << tmp.mxsum << endl;
		}
		else if(op == 2){
			int x, y, k; cin >> x >> y >> k;
			update_path(x, y, k);
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); //cout.tie(0);
	
	int t = 1;
	//cin >> t; 
	while(t --) solve();
	
	return 0;
}