Language: C++

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

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];

ll dfs1(ll now, ll o,int nd)
{
	if (nd > 200000)
	{
		exit(0);
	}
	ll maxw = 0;
	for (auto i : hen[now])
	{
		if (i != o)
		{
			maxw = max(maxw, dfs1(i, nownd + 1));
		}
	}
	deep[now] = maxw + 1;
	return maxw + 1;
}

void dfs2(ll now, ll o, ll b, ll nd, ll pd)
{
	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)
			{
				dfs2(i, now, b, nd + 1, pd);
				sude = true;
			}
			else
			{
				tyo[tn] = point(deep[i], b, nd, pd + 1);
				tn++;
				dfs2(i, now, tn - 1, 0, pd + 1);
			}
		}
	}
}

bool flg;

void heavy()
{
	dfs1(0, -1,0);
	if (flg)
	{
		exit(0);
	}
	tyo[0] = point(deep[0], -1, -1, 0);
	tn = 1;
	dfs2(0, -1, 0, 0, 0);
	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()
{
	int n, q;
	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:63:22: error: 'log2' was not declared in this scope
   63 |                 dw = log2(nw) + 1;
      |                      ^~~~
a.cc: In function 'll dfs1(ll, ll, int)':
a.cc:166:50: error: 'nownd' was not declared in this scope; did you mean 'now'?
  166 |                         maxw = max(maxw, dfs1(i, nownd + 1));
      |                                                  ^~~~~
      |                                                  now