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 << 50);

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 = dw;
		n = max((ll)0, dw);
	}
};

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;
	long dw;
	long o;
	long ob;
	long n;
	long pd;

	point() = default;

	point(long nw, long ow, long obw, long pdw)
	{
		dw = log2(nw) + 1;
		f = (ll*)malloc(8 * 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(long p, long b, long e, long nb, long 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(long b, long e, ll d)
	{
		setw(0, b, e, 0, (1 << dw), d);
	}

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

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

point tyo[222222];
long tn;

ll myd[222222];
vector<int> hen[222222];
long deep[222222];
long syo[222222];
long syod[222222];

long dfs1(long now, long o)
{
	long maxw = 0;
	for (auto i : hen[now])
	{
		if (i != o)
		{
			maxw = max(maxw, dfs1(i, now));
		}
	}
	deep[now] = maxw + 1;
	return maxw + 1;
}

void dfs2(long now, long o, long b, long nd, long 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);
			}
		}
	}
}

void heavy()
{
	dfs1(0, -1);
	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(long a, long b, ll d)
{
	long ab = syo[a];
	long bb = syo[b];
	long ad = syod[a];
	long 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(long a, long b)
{
	node aw = node(-inf, 0);
	node bw = node(-inf, 0);
	long ab = syo[a];
	long bb = syo[b];
	long ad = syod[a];
	long 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()
{
	long 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++)
	{
		long a, b;
		scanf("%d%d", &a, &b);
		a--;
		b--;
		hen[a].push_back(b);
		hen[b].push_back(a);
	}
	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(long int, long int, long int, long int)':
a.cc:63:22: error: 'log2' was not declared in this scope
   63 |                 dw = log2(nw) + 1;
      |                      ^~~~