Language: C++

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

typedef long long ll;

const ll inf = ((ll)1 << 14);

class node
{
public:
	ll d;
	ll s;
	ll b;
	ll a;
	ll m;
	ll n;

	node() = default;

	node(ll dw, ll k)
	{
		d = dw;
		s = max((ll)0, d * k);
		b = max((ll)0, d * k);
		a = d * k;
		m = d;
		n = max((ll)0, d * k);
	}
};

node unit(node a, node b)
{
	node w;
	w.d = -inf;
	w.s = max(a.s, a.a + b.s);
	w.b = max(b.b, b.a + a.b);
	w.a = a.a + b.a;
	w.m = max(a.m, b.m);
	w.n = max(a.b + b.s, max(a.n, b.n));
	return w;
}

class point
{
public:
	ll* f;
	node* seg;
	ll dw;
	ll o;
	ll ob;
	ll n;
	ll pd;

	point() = default;

	point(ll nw, ll ow, ll obw, ll pdw)
	{
		dw = log2(nw) + 1;
		f = (ll*)malloc(sizeof(ll) * nw);
		seg = (node*)malloc(sizeof(node) * (1 << (dw + 1)));
		o = ow;
		ob = obw;
		n = nw;
		pd = pdw;
	}

	void start()
	{
		for (int i = 0; i < (1 << dw); i++)
		{
			if (i < n)
			{
				seg[(1 << dw) - 1 + i] = node(f[i], 1);
			}
			else
			{
				seg[(1 << dw) - 1 + i] = node(-inf, 1);
			}
		}
		for (int i = (1 << dw) - 2; i >= 0; i--)
		{
			seg[i] = unit(seg[i * 2 + 1], seg[i * 2 + 2]);
		}
	}

	void setw(ll p, ll b, ll e, ll nb, ll ne, ll d)
	{
		if (e <= nb || ne <= b)
		{
			return;
		}
		if (b <= nb && ne <= e)
		{
			seg[p] = node(d, ne - nb);
		}
		else
		{
			if (seg[p].d != -inf)
			{
				setw(p * 2 + 1, nb, ne, nb, (nb + ne) / 2, seg[p].d);
				setw(p * 2 + 2, nb, ne, (nb + ne) / 2, ne, seg[p].d);
			}
			setw(p * 2 + 1, b, e, nb, (nb + ne) / 2, d);
			setw(p * 2 + 2, b, e, (nb + ne) / 2, ne, d);
			seg[p] = unit(seg[p * 2 + 1], seg[p * 2 + 2]);
		}
	}

	void set(ll b, ll e, ll d)
	{
		setw(0, b, e, 0, (1 << dw), d);
	}

	node getw(ll p, ll b, ll e, ll nb, ll ne)
	{
		if (e <= nb || ne <= b)
		{
			return node(-inf, 0);
		}
		if (b <= nb && ne <= e)
		{
			return seg[p];
		}
		else
		{
			if (seg[p].d != -inf)
			{
				setw(p * 2 + 1, nb, ne, nb, (nb + ne) / 2, seg[p].d);
				setw(p * 2 + 2, nb, ne, (nb + ne) / 2, ne, seg[p].d);
			}
			return unit(getw(p * 2 + 1, b, e, nb, (nb + ne) / 2), getw(p * 2 + 2, b, e, (nb + ne) / 2, ne));
		}
	}

	node get(ll b, ll e)
	{
		return getw(0, b, e, 0, (1 << dw));
	}
};

point tyo[200000];
ll tn;

ll myd[200000];
vector<ll> hen[200000];
ll deep[200000];
ll syo[200000];
ll syod[200000];

int n, q;
bool flg;

stack<pair<long, long>> st1, st2;

class pw
{
public:
	ll now, o, b, nd, pd;

	pw(ll noww, ll ow, ll bw, ll ndw, ll pdw)
	{
		now = noww;
		o = ow;
		b = bw;
		nd = ndw;
		pd = pdw;
	}
};

stack<pw> st3;

void heavy()
{
	for (int i = 0; i < n; i++)
	{
		deep[i] = 1;
	}
	st1.push(make_pair(0, -1));
	while (!st1.empty())
	{
		long b = st1.top().first;
		long o = st1.top().second;
		st2.push(st1.top());
		st1.pop();
		for (auto i : hen[b])
		{
			if (i != o)
			{
				st1.push(make_pair(i, b));
			}
		}
	}
	while (!st2.empty())
	{
		long b = st2.top().first;
		long o = st2.top().second;
		st2.pop();
		ll maxw = 1;
		for (auto i : hen[b])
		{
			if (i != o)
			{
				maxw = max(maxw, deep[i] + 1);
			}
		}
		deep[b] = maxw;
	}
	tyo[0] = point(deep[0], -1, -1, 0);
	tn = 1;
	st3.push(pw(0, -1, 0, 0, 0));
	while (!st3.empty())
	{
		ll now = st3.top().now;
		ll o = st3.top().o;
		ll b = st3.top().b;
		ll nd = st3.top().nd;
		ll pd = st3.top().pd;
		st3.pop();
		tyo[b].f[nd] = myd[now];
		syo[now] = b;
		syod[now] = nd;
		bool sude = false;
		for (auto i : hen[now])
		{
			if (i != o)
			{
				if (!sude && deep[now] == deep[i] + 1)
				{
					st3.push(pw(i, now, b, nd + 1, pd));
					sude = true;
				}
				else
				{
					tyo[tn] = point(deep[i], b, nd, pd + 1);
					tn++;
					st3.push((i, now, tn - 1, 0, pd + 1));
				}
			}
		}
	}
	for (int i = 0; i < tn; i++)
	{
		tyo[i].start();
	}
}

void set(ll a, ll b, ll d)
{
	ll ab = syo[a];
	ll bb = syo[b];
	ll ad = syod[a];
	ll bd = syod[b];
	while (ab != bb)
	{
		if (tyo[ab].pd > tyo[bb].pd)
		{
			tyo[ab].set(0, ad + 1, d);
			ad = tyo[ab].ob;
			ab = tyo[ab].o;
		}
		else
		{
			tyo[bb].set(0, bd + 1, d);
			bd = tyo[bb].ob;
			bb = tyo[bb].o;
		}
	}
	tyo[ab].set(min(ad, bd), max(ad, bd) + 1, d);
	/*for (int i = 0; i < (1 << (tyo[ab].dw + 1)) - 1; i++)
	{
	printf("%d:%lld %lld %lld %lld %lld %lld\n", i, tyo[ab].seg[i].d, tyo[ab].seg[i].a, tyo[ab].seg[i].s, tyo[ab].seg[i].b, tyo[ab].seg[i].m, tyo[ab].seg[i].n);
	}
	printf("\n");*/
}

node rev(node a)
{
	ll w = a.s;
	a.s = a.b;
	a.b = w;
	return a;
}

ll get(ll a, ll b)
{
	node aw = node(-inf, 0);
	node bw = node(-inf, 0);
	ll ab = syo[a];
	ll bb = syo[b];
	ll ad = syod[a];
	ll bd = syod[b];
	while (ab != bb)
	{
		if (tyo[ab].pd > tyo[bb].pd)
		{
			aw = unit(aw, rev(tyo[ab].get(0, ad + 1)));
			ad = tyo[ab].ob;
			ab = tyo[ab].o;
		}
		else
		{
			bw = unit(bw, rev(tyo[bb].get(0, bd + 1)));
			bd = tyo[bb].ob;
			bb = tyo[bb].o;
		}
	}
	if (bd < ad)
	{
		aw = unit(aw, rev(tyo[ab].get(bd, ad + 1)));
	}
	else
	{
		bw = unit(bw, rev(tyo[ab].get(ad, bd + 1)));
	}
	aw = unit(aw, rev(bw));
	/*printf("%d:%lld %lld %lld %lld %lld %lld\n", 0, aw.d, aw.a, aw.s, aw.b, aw.m, aw.n);
	printf("%d:%lld %lld %lld %lld %lld %lld\n", 1, bw.d, bw.a, bw.s, bw.b, bw.m, bw.n);*/
	if (aw.m < 0)
	{
		return aw.m;
	}
	else
	{
		return aw.n;
	}
}

int main()
{
	scanf("%d%d", &n, &q);
	for (int i = 0; i < n; i++)
	{
		scanf("%lld", &myd[i]);
	}
	for (int i = 0; i < n - 1; i++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		a--;
		b--;
		hen[a].push_back(b);
		hen[b].push_back(a);
	}
	if (n > 150000)
	{
		flg = true;
	}
	else
	{
		flg = false;
	}
	heavy();
	for (int i = 0; i < q; i++)
	{
		ll t, a, b, c;
		scanf("%lld%lld%lld%lld", &t, &a, &b, &c);
		a--;
		b--;
		if (t == 1)
		{
			set(a, b, c);
		}
		else
		{
			printf("%lld\n", get(a, b));
		}
	}
	return 0;
}

Compiler output:
a.cc: In constructor 'point::point(ll, ll, ll, ll)':
a.cc:64:22: error: 'log2' was not declared in this scope
   64 |                 dw = log2(nw) + 1;
      |                      ^~~~
a.cc: In function 'void heavy()':
a.cc:242:49: error: no matching function for call to 'std::stack<pw>::push(ll)'
  242 |                                         st3.push((i, now, tn - 1, 0, pd + 1));
      |                                         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/stack:63,
                 from a.cc:6:
/usr/include/c++/14/bits/stl_stack.h:258:7: note: candidate: 'void std::stack<_Tp, _Sequence>::push(const value_type&) [with _Tp = pw; _Sequence = std::deque<pw, std::allocator<pw> >; value_type = pw]'
  258 |       push(const value_type& __x)
      |       ^~~~
/usr/include/c++/14/bits/stl_stack.h:258:30: note:   no known conversion for argument 1 from 'll' {aka 'long long int'} to 'const std::stack<pw>::value_type&' {aka 'const pw&'}
  258 |       push(const value_type& __x)
      |            ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/14/bits/stl_stack.h:263:7: note: candidate: 'void std::stack<_Tp, _Sequence>::push(value_type&&) [with _Tp = pw; _Sequence = std::deque<pw, std::allocator<pw> >; value_type = pw]'
  263 |       push(value_type&& __x)
      |       ^~~~
/usr/include/c++/14/bits/stl_stack.h:263:25: note:   no known conversion for argument 1 from 'll' {aka 'long long int'} to 'std::stack<pw>::value_type&&' {aka 'pw&&'}
  263 |       push(value_type&& __x)
      |            ~~~~~~~~~~~~~^~~