Language: C++

#define _CRT_SECURE_NO_WARNINGS
#define NDEBUG
#include <cassert>
#include <utility>
#include <vector>
#include<functional>

template <typename ValueMonoid, typename OperatorMonoid, class Modify>
class LinkCutTree {
public:
	using value_type = ValueMonoid;
	using operator_type = OperatorMonoid;

private:
	struct node_t {
		node_t *left, *right, *par;
		value_type value, sum;
		operator_type lazy;
		bool isroot, reversed;
		node_t()
			: left(nullptr), right(nullptr), par(nullptr), value(), sum(), lazy(),
			isroot(1), reversed(0) {}
		node_t(node_t *const l, node_t *const r, node_t *const p,
			const value_type &v)
			: left(l), right(r), par(p), value(v), sum(v), lazy(), isroot(1),
			reversed(0) {}
		bool isleft() const { return par->left == this; }
		void assign(const operator_type &data) { lazy = lazy + data; }
		void haulL(node_t *const t) { left = t, t->par = this; }
		void haulR(node_t *const t) { right = t, t->par = this; }
	};
	value_type reflect(const node_t *const t) const {
		return m(t->reversed ? ~t->sum : t->sum, t->lazy);
	}
	void recalc(node_t *const t) {
		t->sum = reflect(t->left) + t->value + reflect(t->right);
	}
	void splay(node_t *const t) {
		node_t *p, *pp = t, *x = t->par;
		while (!t->isroot) {
			(x->left == pp ? x->left : x->right) = t;
			p = t->par;
			if (p->isroot) {
				t->par = p->par;
				std::swap(t->isroot, p->isroot);
				if (p->left == t)
					p->haulL(t->right), t->haulR(p);
				else
					p->haulR(t->left), t->haulL(p);
				recalc(p);
				break;
			}
			pp = p->par;
			x = pp->par;
			std::swap(t->isroot, pp->isroot);
			if (t->isleft()) {
				if (p->isleft())
					pp->haulL(p->right), p->haulR(pp);
				else
					pp->haulR(t->left), t->haulL(pp);
				p->haulL(t->right);
				t->haulR(p);
			}
			else {
				if (p->isleft())
					pp->haulL(t->right), t->haulR(pp);
				else
					pp->haulR(p->left), p->haulL(pp);
				p->haulR(t->left);
				t->haulL(p);
			}
			recalc(pp);
			recalc(p);
			t->par = x;
		}
	}
	void push(node_t *const t) {
		t->left->assign(t->lazy);
		t->right->assign(t->lazy);
		t->value = m(t->value, t->lazy);
		t->lazy = operator_type();
		if (!t->reversed)
			return;
		std::swap(t->left, t->right);
		t->left->reversed ^= 1;
		t->right->reversed ^= 1;
		t->value = ~t->value;
		t->reversed = 0;
	}
	void propagate(node_t *t) {
		node_t *prev = nullptr;
		do {
			std::swap(t->par, prev);
			std::swap(t, prev);
		} while (t != nil);
		do {
			push(prev);
			std::swap(prev->par, t);
			std::swap(prev, t);
		} while (prev);
		nil->lazy = operator_type();
	}
	void expose(node_t *const n) {
		propagate(n);
		node_t *x = n, *prev = nil;
		do {
			splay(x);
			x->right->isroot = 1;
			x->right = prev;
			prev->isroot = 0;
			recalc(x);
			prev = x;
			x = x->par;
		} while (x != nil);
		splay(n);
		recalc(n);
	}
	using container_type = std::vector<node_t>;

public:
	using size_type = typename container_type::size_type;

private:
	node_t *const nil;
	const Modify m;
	container_type tree;
	void reroot(const size_type v) {
		expose(&tree[v]);
		tree[v].reversed ^= 1;
	}

public:
	explicit LinkCutTree(const size_type size, const Modify &m = Modify())
		: m(m), nil(new node_t), tree(size, node_t(nil, nil, nil, value_type())) {
	}
	explicit LinkCutTree(const std::vector<value_type> &a,
		const Modify &m = Modify())
		: m(m), nil(new node_t) {
		tree.reserve(a.size());
		for (const auto &e : a)
			tree.emplace_back(nil, nil, nil, e);
	}
	~LinkCutTree() { delete nil; }
	void link(const size_type child, const size_type parent) {
		assert(child < size());
		assert(parent < size());
		reroot(child);
		tree[child].par = &tree[parent];
	}
	void cut(const size_type child) {
		assert(child < size());
		node_t *const n = &tree[child];
		expose(n);
		n->left->isroot = 1;
		n->left->par = nil;
		n->left = nil;
		n->sum = n->value;
	}
	bool connected(const size_type u, const size_type v) {
		assert(u < size());
		assert(v < size());
		expose(&tree[u]);
		expose(&tree[v]);
		return tree[u].par != nil;
	}
	void update(const size_type v,
		const std::function<value_type(const value_type &)> &f) {
		assert(v < size());
		expose(&tree[v]);
		tree[v].value = f(tree[v].value);
		recalc(&tree[v]);
	}
	void update(const size_type u, const size_type v, const operator_type &data) {
		assert(u < size());
		assert(v < size());
		reroot(u);
		expose(&tree[v]);
		tree[v].assign(data);
	}
	value_type path(const size_type u, const size_type v) {
		assert(u < size());
		assert(v < size());
		reroot(u);
		expose(&tree[v]);
		return tree[v].sum;
	}
	size_type size() const noexcept { return tree.size(); }
	bool empty() const noexcept { return tree.empty(); }
};

#include <algorithm>
struct Ass {
	int a;
	bool f;
	Ass() : f(1) {}
	Ass(int a) : a(a), f(0) {}
	Ass operator+(const Ass &o) const { return o.f ? *this : o; }
};
struct Line {
	int all, l, r, max, siz;
	bool f;
	Line() : f(1) {}
	Line(int all, int l, int r, int max, int siz, bool f = 0)
		: all(all), l(l), r(r), max(max), siz(siz), f(f) {}
	Line operator~() const { return Line(all, r, l, max, siz, f); }
	Line operator+(const Line &o) const {
		if (f)
			return o;
		if (o.f)
			return *this;
		return Line(all + o.all, std::max(l, o.l > 0 ? all + o.l : all),
			std::max(o.r, r > 0 ? r + o.all : o.all),
			std::max(std::max(max, o.max), r + o.l), siz + o.siz);
	}
};
struct hoge {
	Line operator()(const Line &x, const Ass &y) const {
		if (y.f || x.f)
			return x;
		if (y.a > 0)
			return Line(y.a * x.siz, y.a * x.siz, y.a * x.siz, y.a * x.siz, x.siz);
		else
			return Line(y.a * x.siz, y.a, y.a, y.a, x.siz);
	}
};

template <typename T> scan(T &d) { d = 0; }
#include <cstdio>
#include <vector>
int main(void) {
	int nn, q;
	scanf("%d %d", &nn, &q);
	const int n = nn;
	std::vector<Line> d;
	int w;
	for (int i = 0; i < n; ++i) {
		scanf("%d", &w);
		d.emplace_back(w, w, w, w, 1);
	}
	LinkCutTree<Line, Ass, hoge> T(d);
	int s, e;
	for (int i = 1; i < n; ++i) {
		scanf("%d %d", &s, &e);
		T.link(s - 1, e - 1);
	}
	int t, a, b;
	Ass c(0);
	while (q--) {
		scanf("%d %d %d %d", &t, &a, &b, &c.a);
		if (t == 1)
			T.update(a - 1, b - 1, c);
		else
			printf("%d\n", T.path(a - 1, b - 1).max);
	}
	return 0;
}


Compiler output:
a.cc:227:23: error: ISO C++ forbids declaration of 'scan' with no type [-fpermissive]
  227 | template <typename T> scan(T &d) { d = 0; }
      |                       ^~~~
a.cc: In function 'int scan(T&)':
a.cc:227:43: warning: no return statement in function returning non-void [-Wreturn-type]
  227 | template <typename T> scan(T &d) { d = 0; }
      |                                           ^