没有科技上不了SPOJ

代码最后那个小hack过了

#include <bits/stdc++.h>
using namespace std;
namespace lgh {
#define int long long
	
mt19937 rnd(time(nullptr));
int rand(int l, int r) {
	return l + labs(rnd()) % (r - l + 1);
}
	
const int N = 5e4 + 5;
const int INF = 0x3f3f3f3f;
	
int n;
int w[N];
	
struct Edge {
	int to, pre;
};
Edge e[N * 2];
int idx = 1, head[N];
void addedge(int u, int v) {
	e[++idx] = {v, head[u]};
	head[u] = idx;
}
	
int dep[N], fa[N], siz[N], hson[N];
int dfn[N], rnk[N], index, top[N];
void dfs1(int u, int lst) {
	siz[u] = 1;
	for(int i = head[u]; i; i = e[i].pre) {
		int v = e[i].to;
		if(v == lst) continue;
		dep[v] = dep[u] + 1;
		fa[v] = u;
		dfs1(v, u);
		siz[u] += siz[v];
		if(siz[v] > siz[hson[u]])
			hson[u] = v;
	}
}
void dfs2(int u, int lst, int tp) {
	dfn[u] = ++index; rnk[index] = u;
	top[u] = tp;
	if(!hson[u]) return;
	dfs2(hson[u], u, tp);
	for(int i = head[u]; i; i = e[i].pre) {
		int v = e[i].to;
		if(v == lst) continue;
		if(v == hson[u]) continue;
		dfs2(v, u, v);
	}
}
	
struct Segtree {
	int sub, presub, sufsub, sum, cov;
	Segtree() {
		sub = 0;
		presub = 0;
		sufsub = 0;
		sum = 0;
		cov = INF;
	}
};
Segtree seg[N * 4];
void pushup(int o) {
	int ls = o << 1, rs = o << 1 | 1;
	seg[o].sub = max(max(seg[ls].sub, seg[rs].sub), seg[ls].sufsub + seg[rs].presub);
	seg[o].presub = max(seg[ls].presub, seg[ls].sum + seg[rs].presub);
	seg[o].sufsub = max(seg[rs].sufsub, seg[rs].sum + seg[ls].sufsub);
	seg[o].sum = seg[ls].sum + seg[rs].sum;
}
void build(int o, int l, int r) {
	if(l == r) {
		seg[o].sub = max(w[rnk[l]], 0ll);
		seg[o].presub = max(w[rnk[l]], 0ll);
		seg[o].sufsub = max(w[rnk[l]], 0ll);
		seg[o].sum = w[rnk[l]];
		return;
	}
	int mid = l + (r - l) / 2, ls = o << 1, rs = o << 1 | 1;
	build(ls, l, mid);
	build(rs, mid + 1, r);
	pushup(o);
}
void pushdown(int o, int l, int r) {
	int mid = l + (r - l) / 2, ls = o << 1, rs = o << 1 | 1;
	seg[ls].sub = max(seg[o].cov * (mid - l + 1), 0ll);
	seg[rs].sub = max(seg[o].cov * (r - mid), 0ll);
	seg[ls].presub = max(seg[o].cov * (mid - l + 1), 0ll);
	seg[rs].presub = max(seg[o].cov * (r - mid), 0ll);
	seg[ls].sufsub = max(seg[o].cov * (mid - l + 1), 0ll);
	seg[rs].sufsub = max(seg[o].cov * (r - mid), 0ll);
	seg[ls].sum = seg[o].cov * (mid - l + 1);
	seg[rs].sum = seg[o].cov * (r - mid);
	seg[ls].cov = seg[o].cov;
	seg[rs].cov = seg[o].cov;
	seg[o].cov = INF;
}
void update(int o, int l, int r, int x, int y, int d) {
	if(x <= l && r <= y) {
		seg[o].sub = max(d * (r - l + 1), 0ll);
		seg[o].presub = max(d * (r - l + 1), 0ll);
		seg[o].sufsub = max(d * (r - l + 1), 0ll);
		seg[o].sum = d * (r - l + 1);
		seg[o].cov = d;
		return;
	}
	if(seg[o].cov != INF) pushdown(o, l, r);
	int mid = l + (r - l) / 2, ls = o << 1, rs = o << 1 | 1;
	if(x <= mid) update(ls, l, mid, x, y, d);
	if(y > mid) update(rs, mid + 1, r, x, y, d);
	pushup(o);
}
Segtree merge(const Segtree &a, const Segtree &b) {
	Segtree res;
	res.sub = max(max(a.sub, b.sub), a.sufsub + b.presub);
	res.presub = max(a.presub, a.sum + b.presub);
	res.sufsub = max(b.sufsub, b.sum + a.sufsub);
	res.sum = a.sum + b.sum;
	return res;
}
Segtree query(int o, int l, int r, int x, int y) {
	if(x <= l && r <= y) return seg[o];
	if(seg[o].cov != INF) pushdown(o, l, r);
	int mid = l + (r - l) / 2, ls = o << 1, rs = o << 1 | 1;
	if(y <= mid) return query(ls, l, mid, x, y);
	if(x > mid) return query(rs, mid + 1, r, x, y);
	Segtree lson = query(ls, l, mid, x, y);
	Segtree rson = query(rs, mid + 1, r, x, y);
	return merge(lson, rson);
}

void upd(int x, int y, int d) {
	while(top[x] != top[y]) {
		if(dep[top[x]] < dep[top[y]]) swap(x, y);
		update(1, 1, n, dfn[top[x]], dfn[x], d);
		x = fa[top[x]];
	}
	if(dep[x] > dep[y]) swap(x, y);
	update(1, 1, n, dfn[x], dfn[y], d);
}
Segtree que(int x, int y) {
	Segtree l, r;
	while(top[x] != top[y]) {
		if(dep[top[x]] < dep[top[y]]) swap(x, y), swap(l, r);
		auto tmp = query(1, 1, n, dfn[top[x]], dfn[x]);
		l = merge(l, tmp);
		x = fa[top[x]];
	}
	if(dep[x] > dep[y]) swap(x, y), swap(l, r);
	auto tmp = query(1, 1, n, dfn[x], dfn[y]);
	swap(l.presub, l.sufsub);
	l = merge(l, tmp);
	return merge(l, r);
}
	
signed main() {	
	scanf(" %lld", &n);
	for(int i = 1; i <= n; ++i) scanf(" %lld", &w[i]);
	for(int i = 1; i <= n - 1; ++i) {
		int u, v;
		scanf(" %lld %lld", &u, &v);
		addedge(u, v);
		addedge(v, u);
	}
	
//	int S = rand(1, n);
	int S = 1;
	dfs1(S, 0);
	dfs2(S, 0, S);
	dep[0] = -1;
	
	build(1, 1, n);
	int Q; scanf(" %lld", &Q); while(Q--) {
		int opt;
		scanf(" %lld", &opt);
		if(opt == 1) {
			int x, y;
			scanf(" %lld %lld", &x, &y);
			auto tmp = que(x, y);
			printf("%lld\n", tmp.sub);
		}
		if(opt == 2) {
			int x, y, z;
			scanf(" %lld %lld %lld", &x, &y, &z);
			upd(x, y, z);
		}
	}
	return 0;
}
}
signed main() {
//	freopen("3.in", "r", stdin);
//	freopen("3.out", "w", stdout);
	return lgh::main();
}

/*
hack1:
5
-3 -2 -1 -2 -3
1 2
2 3
1 4
4 5
2	
2 3 4 2
1 2 5
ans1:
6
*/