#include <vector>
#include <iostream>
#include <stack>
#include <utility>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;


namespace libcomp {
namespace structure {


template <typename T>
struct SumLazySegmentTreeTraits {
	typedef T value_type;
	typedef T modifier_type;

	value_type default_value() const { return 0; }
	modifier_type default_modifier() const { return 0; }

	value_type merge_value(
		const value_type &a, const value_type &b) const
	{
		return a + b;
	}
	modifier_type merge_modifier(
		const modifier_type &a, const modifier_type &b) const
	{
		return a + b;
	}
	value_type resolve(
		int a, int b, const value_type &val, const modifier_type &mod) const
	{
		return val + (b - a) * mod;
	}

};

template <typename Traits>
class LazySegmentTree {

public:
	typedef typename Traits::value_type value_type;
	typedef typename Traits::modifier_type modifier_type;

private:
	Traits m_traits;
	vector<value_type> m_values;
	vector<modifier_type> m_modifiers;
	size_t m_size;

	void initialize(){
		for(int i = static_cast<int>(m_size) - 2; i >= 0; --i){
			m_values[i] = m_traits.merge_value(
				m_values[i * 2 + 1], m_values[i * 2 + 2]);
		}
	}

	value_type modify(
		int a, int b, int k, int l, int r, const modifier_type &modifier)
	{
		if(r <= a || b <= l){
			return m_traits.resolve(l, r, m_values[k], m_modifiers[k]);
		}
		if(a <= l && r <= b){
			m_modifiers[k] =
				m_traits.merge_modifier(m_modifiers[k], modifier);
			return m_traits.resolve(l, r, m_values[k], m_modifiers[k]);
		}
		const modifier_type prev = m_modifiers[k];
		m_modifiers[k] = m_traits.default_modifier();
		const int c = (l + r) / 2, lk = k * 2 + 1, rk = k * 2 + 2;
		m_modifiers[lk] = m_traits.merge_modifier(prev, m_modifiers[lk]);
		m_modifiers[rk] = m_traits.merge_modifier(prev, m_modifiers[rk]);
		const value_type vl = modify(a, b, lk, l, c, modifier);
		const value_type vr = modify(a, b, rk, c, r, modifier);
		m_values[k] = m_traits.merge_value(vl, vr);
		return m_values[k];
	}

	value_type query(int a, int b, int k, int l, int r){
		if(r <= a || b <= l){ return m_traits.default_value(); }
		if(a <= l && r <= b){
			return m_traits.resolve(l, r, m_values[k], m_modifiers[k]);
		}
		const modifier_type modifier = m_modifiers[k];
		m_values[k] = m_traits.resolve(l, r, m_values[k], modifier);
		m_modifiers[k] = m_traits.default_modifier();
		const int c = (l + r) / 2, lk = k * 2 + 1, rk = k * 2 + 2;
		m_modifiers[lk] = m_traits.merge_modifier(m_modifiers[lk], modifier);
		m_modifiers[rk] = m_traits.merge_modifier(m_modifiers[rk], modifier);
		const value_type vl = query(a, b, lk, l, c);
		const value_type vr = query(a, b, rk, c, r);
		return m_traits.merge_value(vl, vr);
	}

public:
	explicit LazySegmentTree(
		size_t size = 0, const Traits &traits = Traits()) :
		m_size(1), m_traits(traits)
	{
		while(m_size < size){ m_size *= 2; }
		m_values.resize(m_size * 2 - 1, m_traits.default_value());
		m_modifiers.resize(m_size * 2 - 1, m_traits.default_modifier());
		initialize();
	}

	template <typename Iterator>
	LazySegmentTree(
		Iterator first, Iterator last, const Traits &traits = Traits()) :
		m_size(1), m_traits(traits)
	{
		const size_t n = distance(first, last);
		while(m_size < n){ m_size *= 2; }
		m_values.resize(m_size * 2 - 1, m_traits.default_value());
		m_modifiers.resize(m_size * 2 - 1, m_traits.default_modifier());
		copy(first, last, m_values.begin() + m_size - 1);
		initialize();
	}

	void modify(int a, int b, const modifier_type &modifier){
		modify(a, b, 0, 0, m_size, modifier);
	}

	value_type query(int a, int b){
		return query(a, b, 0, 0, m_size);
	}

};


}
}


namespace libcomp {
namespace graph {


class HeavyLightDecomposer {

public:
	struct Connection {
		int local_index;
		int child_path;

		explicit Connection(int li = -1, int cp = -1) :
			local_index(li), child_path(cp)
		{ }
	};

	struct Segment {
		int path;
		int first;
		int last;

		explicit Segment(int path = -1, int first = -1, int last = -1) :
			path(path), first(first), last(last)
		{ }
	};

private:
	typedef pair<int, int> pii;

	struct Path {
		int parent_vertex;
		vector<Connection> children;
		vector<int> vertices;
		int depth;
	};

	vector<Path> m_paths;
	vector<int> m_path_ids;
	vector<int> m_local_indices;

	template <typename EDGE_TYPE>
	vector<int> compute_subtree_size(
		const vector< vector<EDGE_TYPE> > &conn, int root) const
	{
		const int n = conn.size();
		vector<int> subtree_size(n);
		vector<bool> passed(n), gathered(n);
		stack<pii> count_stack;
		count_stack.push(pii(root, 0));
		while(!count_stack.empty()){
			const pii p = count_stack.top();
			count_stack.pop();
			const int u = p.first, i = p.second;
			if(i == 0){
				passed[u] = true;
				count_stack.push(pii(u, 1));
				for(int j = 0; j < conn[u].size(); ++j){
					const int v = conn[u][j].to;
					if(passed[v]){ continue; }
					count_stack.push(pii(v, 0));
				}
			}else{
				int sum = 1;
				gathered[u] = true;
				for(int j = 0; j < conn[u].size(); ++j){
					const int v = conn[u][j].to;
					if(!gathered[v]){ continue; }
					sum += subtree_size[v];
				}
				subtree_size[u] = sum;
			}
		}
		return subtree_size;
	}

public:
	HeavyLightDecomposer() :
		m_paths(0), m_path_ids(0), m_local_indices(0)
	{ }

	template <typename EDGE_TYPE>
	explicit HeavyLightDecomposer(
		const vector< vector<EDGE_TYPE> > &conn, int root = 0) :
		m_paths(0), m_path_ids(conn.size(), -1),
		m_local_indices(conn.size(), -1)
	{
		const int n = conn.size();
		const vector<int> subtree_size = compute_subtree_size(conn, root);
		stack<pii> decompose_stack;
		decompose_stack.push(pii(root, -1));
		while(!decompose_stack.empty()){
			const pii p = decompose_stack.top();
			decompose_stack.pop();
			const int parent_vertex = p.second;
			const int pid = m_paths.size();
			m_paths.push_back(Path());
			Path &path = m_paths.back();
			path.parent_vertex = parent_vertex;
			if(parent_vertex >= 0){
				const int parent_pid = m_path_ids[parent_vertex];
				const int parent_index = m_local_indices[parent_vertex];
				m_paths[parent_pid].children.push_back(
					Connection(parent_index, pid));
				path.depth = m_paths[parent_pid].depth + 1;
			}else{
				path.depth = 0;
			}
			int cur = p.first;
			while(cur >= 0){
				const int st_size = subtree_size[cur], threshold = st_size / 2;
				m_path_ids[cur] = pid;
				m_local_indices[cur] = path.vertices.size();
				path.vertices.push_back(cur);
				int heavy_edge = -1;
				for(int i = 0; i < conn[cur].size(); ++i){
					const int v = conn[cur][i].to;
					if(subtree_size[v] > subtree_size[cur]){ continue; }
					if(heavy_edge < 0 && subtree_size[v] >= threshold){
						heavy_edge = v;
					}else{
						decompose_stack.push(pii(v, cur));
					}
				}
				cur = heavy_edge;
			}
		}
	}

	int path_count() const { return m_paths.size(); }

	int path_length(int p) const { return m_paths[p].vertices.size(); }

	const vector<Connection> &path_children(int p) const {
		return m_paths[p].children;
	}

	int path_depth(int p) const { return m_paths[p].depth; }

	int parent_vertex_id(int p) const {
		return m_paths[p].parent_vertex;
	}

	int parent_path_id(int p) const {
		if(m_paths[p].parent_vertex < 0){ return -1; }
		return m_path_ids[m_paths[p].parent_vertex];
	}

	int parent_local_index(int p) const {
		if(m_paths[p].parent_vertex < 0){ return -1; }
		return m_local_indices[m_paths[p].parent_vertex];
	}

	int path_id(int v) const { return m_path_ids[v]; }

	int local_index(int v) const { return m_local_indices[v]; }

	int vertex_id(int p, int i) const { return m_paths[p].vertices[i]; }

	vector<Segment> shortest_path(int u, int v) const {
		vector<Segment> usegs, vsegs, result;
		int up = path_id(u), ul = local_index(u);
		int vp = path_id(v), vl = local_index(v);
		while(up != vp){
			const bool update_u = path_depth(up) >= path_depth(vp);
			const bool update_v = path_depth(up) <= path_depth(vp);
			if(update_u){
				usegs.push_back(Segment(up, 0, ul + 1));
				ul = parent_local_index(up);
				up = parent_path_id(up);
			}
			if(update_v){
				vsegs.push_back(Segment(vp, 0, vl + 1));
				vl = parent_local_index(vp);
				vp = parent_path_id(vp);
			}
		}
		for(int i = 0; i < static_cast<int>(usegs.size()); ++i){
			const Segment &s = usegs[i];
			result.push_back(Segment(s.path, s.last - 1, s.first - 1));
		}
		result.push_back(Segment(up, ul, vl + (ul > vl ? -1 : 1)));
		for(int i = static_cast<int>(vsegs.size()) - 1; i >= 0; --i){
			result.push_back(vsegs[i]);
		}
		return result;
	}

};


}
}


using libcomp::structure::LazySegmentTree;
using libcomp::graph::HeavyLightDecomposer;

const ll INF = 1000000000000000000ll;;

struct Edge {
	int to;
	explicit Edge(int to = 0) : to(to) { }
};

struct STValue {
	ll left, right, partial, all;
	explicit STValue(ll l = 0, ll r = 0, ll p = 0, ll a = 0) :
		left(l), right(r), partial(p), all(a)
	{ }
};
struct STModifier {
	ll time_stamp, value;
	explicit STModifier(ll t = 0, ll v = 0) :
		time_stamp(t), value(v)
	{ }
};
struct STTraits {
	typedef STValue value_type;
	typedef STModifier modifier_type;

	value_type default_value() const { return STValue(0, 0, -INF, 0); }
	modifier_type default_modifier() const { return STModifier(-1, 0); }

	STValue merge_value(const STValue &a, const STValue &b) const {
		STValue result;
		if(a.partial < a.all){ return b; }
		if(b.partial < b.all){ return a; }
		result.left = max(a.left, a.all + b.left);
		result.right = max(a.right + b.all, b.right);
		result.partial = max(max(a.partial, b.partial), a.right + b.left);
		result.all = a.all + b.all;
		return result;
	}
	STModifier merge_modifier(const STModifier &a, const STModifier &b) const {
		return (a.time_stamp >= b.time_stamp ? a : b);
	}
	STValue resolve(
		int a, int b, const STValue &val, const STModifier &mod) const
	{
		if(mod.time_stamp < 0){ return val; }
		STValue result;
		if(mod.value > 0){
			result.left = mod.value * (b - a);
			result.right = mod.value * (b - a);
			result.partial = mod.value * (b - a);
			result.all = mod.value * (b - a);
		}else{
			result.left = mod.value;
			result.right = mod.value;
			result.partial = mod.value;
			result.all = mod.value * (b - a);
		}
		return result;
	}
};

int main(){
	ios_base::sync_with_stdio(false);
	int n, q;
	cin >> n >> q;
	vector<int> w(n);
	for(int i = 0; i < n; ++i){ cin >> w[i]; }
	vector< vector<Edge> > conn(n);
	for(int i = 1; i < n; ++i){
		int a, b;
		cin >> a >> b;
		--a; --b;
		conn[a].push_back(Edge(b));
		conn[b].push_back(Edge(a));
	}
	const HeavyLightDecomposer decomp(conn);
	const int m = decomp.path_count();
	vector< LazySegmentTree<STTraits> > segtrees(m);
	for(int i = 0; i < m; ++i){
		const int len = decomp.path_length(i);
		vector<STValue> values(len);
		for(int j = 0; j < len; ++j){
			const int x = w[decomp.vertex_id(i, j)];
			values[j] = STValue(x, x, x, x);
		}
		segtrees[i] = LazySegmentTree<STTraits>(values.begin(), values.end());
	}
	for(int ts = 0; ts < q; ++ts){
		int t, a, b, c;
		cin >> t >> a >> b >> c;
		--a; --b;
		const vector<HeavyLightDecomposer::Segment> route =
			decomp.shortest_path(a, b);
		if(t == 1){
			for(int i = 0; i < route.size(); ++i){
				const int p = route[i].path;
				int first = route[i].first, last = route[i].last;
				if(first > last){
					swap(first, last);
					++first; ++last;
				}
				segtrees[p].modify(first, last, STModifier(ts, c));
			}
		}else if(t == 2){
			const int len = route.size();
			vector<STValue> values(len);
			vector<ll> integral(len + 1);
			ll answer = -INF;
			for(int i = 0; i < len; ++i){
				const int p = route[i].path;
				int first = route[i].first, last = route[i].last;
				if(first > last){
					const STValue v = segtrees[p].query(last + 1, first + 1);
					values[i] = STValue(v.right, v.left, v.partial, v.all);
				}else{
					const STValue v = segtrees[p].query(first, last);
					values[i] = v;
				}
				integral[i] = values[i].all;
				answer = max(answer, values[i].partial);
			}
			ll sum = 0;
			for(int i = 0; i < len; ++i){
				const ll t = integral[i];
				integral[i] = sum;
				sum += t;
			}
			integral.back() = sum;
			for(int l = 0; l < len; ++l){
				for(int r = l + 1; r < len; ++r){
					const ll x = integral[r] - integral[l + 1];
					answer = max(
						answer, values[l].right + values[r].left + x);
				}
			}
			cout << answer << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 64860