Language: C++

#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_DEPRECATE
 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <limits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>
#include <iomanip>
#include <fstream>
#include <iterator>
#include <bitset>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> Pii;
typedef pair<ll, ll> Pll;
 
#define FOR(i,n) for(int i = 0; i < (n); i++)
#define sz(c) ((int)(c).size())
#define ten(x) ((int)1e##x)
#define tenll(x) ((ll)1e##x)
 
#pragma comment(linker,"/STACK:36777216")
 
//heavy-light decomposition
class HL_decomposition {
public:
    const vector<vector<int>>& e;
    const int n;
    vector<int> par, depth, ord; //???,???±?????????????????????????????????
    vector<int> cluster; //decomposition???????????????????????????????????±??????????
    vector<vector<int> > pathes; //?????????????????????????????????????????????
    vector<int> path_idx; // path_idx[v] = ?????¨??????????§???index
 
    void init(int v) {
        depth.resize(n, 0);
        par.resize(n, 0);
        ord.resize(n, 0);
 
        depth[v] = 0;
        par[v] = -1;
        ord[0] = v; //ord????????\??????¨???????????????bfs??????
        for (int p = 0, r = 1; p < r; p++) {
            int cur = ord[p];
            for (int nv : e[cur]) {
                if (nv == par[cur]) continue;
                ord[r++] = nv;
                par[nv] = cur;
                depth[nv] = depth[cur] + 1;
            }
        }
    }
 
    void decomposition() {
        vector<int> subtree_size(n, 1);
        for (int i = n - 1; i > 0; i--) subtree_size[par[ord[i]]] += subtree_size[ord[i]];
        cluster.resize(n, -1);
        int cluster_type = 0;
        FOR(i, n) {
            int u = ord[i];
            if (cluster[u] == -1) cluster[u] = cluster_type++;
            int max_subsize = -1, selected = -1;
            for (int v : e[u]) {
                if (par[u] != v && max_subsize < subtree_size[v]) {
                    max_subsize = subtree_size[v];
                    selected = v;
                }
            }
            if (selected != -1) cluster[selected] = cluster[u];
        }
    }
 
    void enum_pathes() {
        int cluster_num = 0;
        vector<int> rp(n);
        FOR(i, n) {
            rp[cluster[i]]++;
            cluster_num = max(cluster_num, cluster[i]);
        }
        cluster_num++;
        pathes.resize(cluster_num);
        FOR(i, cluster_num) pathes[i].resize(rp[i]);
        for (int i = n - 1; i >= 0; i--) {
            int u = ord[i];
            pathes[cluster[u]][--rp[cluster[u]]] = u;
        }
    }
 
    void set_path_idx() {
        path_idx.resize(n);
        for (const vector<int>& path : pathes) {
            FOR(i, sz(path)) path_idx[path[i]] = i;
        }
    }
 
public:
    HL_decomposition(const vector<vector<int>>& e) : e(e), n(sz(e)) {
        init(0);
        decomposition();
        enum_pathes();
        set_path_idx();
    }
};
 
const int INF = ten(9);
 
struct A {
    int left, right, ans, all;
    bool lazyflag;
    int lazyval;
    A& reverse(){
        std::swap(left, right);
        return *this;
    }
};
 
class DouseTree {
    int n;
    mutable std::vector<A> node;
    void update(int a, int b, int x, int k, int l, int r){
        if (r <= a || b <= l)return;
        if (a <= l && r <= b) {
            A &v = node[k];
            v.left = v.right = v.ans = x <= 0 ? x : x*(r - l);
            v.all = x*(r - l);
            v.lazyflag = true;
            v.lazyval = x;
            return;
        }
        int m = (l + r) / 2;
        if (node[k].lazyflag) {
            update(l, r, node[k].lazyval, 2 * k + 1, l, m);
            update(l, r, node[k].lazyval, 2 * k + 2, m, r);
            node[k].lazyflag = false;
        }
        update(a, b, x, 2 * k + 1, l, m);
        update(a, b, x, 2 * k + 2, m, r);
        node[k] = func(node[2 * k + 1], node[2 * k + 2]);
    }
    A query(int a, int b, int k, int l, int r){
        if (r <= a || b <= l)return identity();
        if (a <= l && r <= b) {
            return node[k];
        }
        int m = (l + r) / 2;
        if (node[k].lazyflag) {
            update(l, r, node[k].lazyval, 2 * k + 1, l, m);
            update(l, r, node[k].lazyval, 2 * k + 2, m, r);
            node[k].lazyflag = false;
        }
        return func(query(a, b, 2 * k + 1, l, m), query(a, b, 2 * k + 2, m, r));
    }
public:
    static A identity(){
        A res = { -INF, -INF, -INF, 0, false };
        return res;
    }
    static A func(const A &a, const A &b){
        if (a.left == -INF)return b;
        if (b.left == -INF)return a;
        A res;
        res.left = max(a.left, a.all + b.left);
        res.right = max(b.right, a.right + b.all);
        res.ans = max(max(a.ans, b.ans), a.right + b.left);
        res.all = a.all + b.all;
        res.lazyflag = false;
        return res;
    }
    DouseTree(int n){
        init(n);
    }
    void init(int n){
        while (n&(n - 1))n += n&-n;
        this->n = n;
        node.assign(2 * n - 1, identity());
    }
    void update(int a, int b, int x){
        update(a, b, x, 0, 0, n);
    }
    A query(int a, int b){
        return query(a, b, 0, 0, n);
    }
};
 
 
class LCA {
public:
    vector<vector<int>>& e;
    int V, logV;
    vector<int> depth;
    vector<vector<int> > parent;
 
    LCA(vector<vector<int>>& e) : e(e) {
        this->V = sz(e);
        logV = 0;
        while (V >= (1 << logV)) logV++;
        this->depth = vector<int>(V);
        this->parent = vector<vector<int> >(logV, vector<int>(V));
 
        dfs(0, -1, 0);
        build();
    }
 
    void dfs(int v, int par, int d) {
        depth[v] = d;
        parent[0][v] = par;
        for (auto to : e[v]) {
            if (par == to) continue;
            dfs(to, v, d + 1);
        }
    }
 
    void build() {
        for (int k = 0; k + 1 < logV; k++) {
            for (int v = 0; v < V; v++) {
                if (parent[k][v] < 0) parent[k + 1][v] = -1;
                else parent[k + 1][v] = parent[k][parent[k][v]];
            }
        }
    }
 
    int prev_parent(int u, int par) {
        for (int k = logV - 1; k >= 0; k--) {
            int diff = depth[u] - depth[par];
            if ((diff - (1 << k)) > 0) {
                u = parent[k][u];
            }
        }
        return u;
    }
 
    int query(int u, int v) {
        if (depth[u] > depth[v]) swap(u, v);
        for (int k = 0; k < logV; k++) {
            if ((depth[v] - depth[u]) >> k & 1)
                v = parent[k][v];
        }
        if (u == v) return u;
 
        for (int k = logV - 1; k >= 0; k--) {
            if (parent[k][u] != parent[k][v]) {
                u = parent[k][u];
                v = parent[k][v];
            }
        }
        return parent[0][u];
    }
};
 
class tree_query {
    LCA* lca;
    HL_decomposition *hl;
    vector<DouseTree*> rmqs;
public:
    tree_query(vector<vector<int>>& e, vector<int>& a) {
        lca = new LCA(e);
        hl = new HL_decomposition(e);
        rmqs.resize(sz(hl->pathes));
        FOR(i, sz(rmqs)) {
            rmqs[i] = new DouseTree(sz(hl->pathes[i]));
            FOR(j, sz(hl->pathes[i])){
                rmqs[i]->update(j, j + 1, a[hl->pathes[i][j]]);
            }
        }
    }
 
    // u -- v ??? u -- lca(u,v) , v - lca(u,v)?????? ????????????
    pair<Pii, Pii> expose(int u, int v) {
        auto l = lca->query(u, v);
        int l2 = -1;
        if (l != v) l2 = lca->prev_parent(v, l);
        return make_pair(Pii(u, l), Pii(v, l2));
    }
 
    void update_core(int u, int par, int val) {
        if (par == -1) return;
        while (true) {
            int l_index = 0;
            if (hl->cluster[u] == hl->cluster[par]) l_index = hl->path_idx[par];
            rmqs[hl->cluster[u]]->update(l_index, hl->path_idx[u] + 1, val);
            if (hl->cluster[u] == hl->cluster[par]) break;
            u = hl->par[hl->pathes[hl->cluster[u]][0]];
        }
    }
 
    void update(int u, int v, int val) {
        auto ep = expose(u, v);
        update_core(ep.first.first, ep.first.second, val);
        update_core(ep.second.first, ep.second.second, val);
    }
 
    A query_core(int u, int par) {
        A ret = DouseTree::identity();
        if (par == -1) return ret;
        while (true) {
            int l_index = 0;
            if (hl->cluster[u] == hl->cluster[par]) l_index = hl->path_idx[par];
            auto cur = rmqs[hl->cluster[u]]->query(l_index, hl->path_idx[u] + 1);
            ret = DouseTree::func(cur, ret);
            if (hl->cluster[u] == hl->cluster[par]) break;
            u = hl->par[hl->pathes[hl->cluster[u]][0]];
        }
        return ret;
    }
 
    ll query(int u, int v) {
        auto ep = expose(u, v);
        auto ans1 = query_core(ep.first.first, ep.first.second);
        auto ans2 = query_core(ep.second.first, ep.second.second);
         
        auto ans =DouseTree::func(ans1.reverse(), ans2);
        return ans.ans;
    }
 
    ~tree_query() {
        delete lca;
        delete hl;
        FOR(i, sz(rmqs)) delete rmqs[i];
    }
};
 
 #ifdef _WIN32
#   define mygc(c) (c)=getchar()
#   define mypc(c) putchar(c)
#else
#   define mygc(c) (c)=getchar_unlocked()
#   define mypc(c) putchar_unlocked(c)
#endif

void reader(int *x) { int k, m = 0; *x = 0; for (;;) { mygc(k); if (k == '-') { m = 1; break; }if ('0' <= k&&k <= '9') { *x = k - '0'; break; } }for (;;) { mygc(k); if (k<'0' || k>'9')break; *x = (*x) * 10 + k - '0'; }if (m)(*x) = -(*x); }
void reader(ll *x) { int k, m = 0; *x = 0; for (;;) { mygc(k); if (k == '-') { m = 1; break; }if ('0' <= k&&k <= '9') { *x = k - '0'; break; } }for (;;) { mygc(k); if (k<'0' || k>'9')break; *x = (*x) * 10 + k - '0'; }if (m)(*x) = -(*x); }
int reader(char c[]) { int i, s = 0; for (;;) { mygc(i); if (i != ' '&&i != '\n'&&i != '\r'&&i != '\t'&&i != EOF) break; }c[s++] = i; for (;;) { mygc(i); if (i == ' ' || i == '\n' || i == '\r' || i == '\t' || i == EOF) break; c[s++] = i; }c[s] = '\0'; return s; }
template <class T, class S> void reader(T *x, S *y) { reader(x); reader(y); }
template <class T, class S, class U> void reader(T *x, S *y, U *z) { reader(x); reader(y); reader(z); }
template <class T, class S, class U, class V> void reader(T *x, S *y, U *z, V *w) { reader(x); reader(y); reader(z); reader(w); }

void writer(int x, char c) { int s = 0, m = 0; char f[10]; if (x<0)m = 1, x = -x; while (x)f[s++] = x % 10, x /= 10; if (!s)f[s++] = 0; if (m)mypc('-'); while (s--)mypc(f[s] + '0'); mypc(c); }
void writer(ll x, char c) { int s = 0, m = 0; char f[20]; if (x<0)m = 1, x = -x; while (x)f[s++] = x % 10, x /= 10; if (!s)f[s++] = 0; if (m)mypc('-'); while (s--)mypc(f[s] + '0'); mypc(c); }
void writer(const char c[]) { int i; for (i = 0; c[i] != '\0'; i++)mypc(c[i]); }
void writer(const char x[], char c) { int i; for (i = 0; x[i] != '\0'; i++)mypc(x[i]); mypc(c); }
template<class T> void writerLn(T x) { writer(x, '\n'); }
template<class T, class S> void writerLn(T x, S y) { writer(x, ' '); writer(y, '\n'); }
template<class T, class S, class U> void writerLn(T x, S y, U z) { writer(x, ' '); writer(y, ' '); writer(z, '\n'); }
template<class T> void writerArr(T x[], int n) { if (!n) { mypc('\n'); return; }FOR(i, n - 1)writer(x[i], ' '); writer(x[n - 1], '\n'); }

int main() {
    int n,m; reader(n,m);
    vector<int> v(n);
    FOR(i, n) reader(v[i]);
    vector<vector<int>> e(n);
    FOR(i, n - 1){
        int a,b; reader(a,b);
        a--; b--;
        e[a].push_back(b);
        e[b].push_back(a);
    }
 
    tree_query tq(e,v);
 
    FOR(i, m){
        int t,a,b,c; reade(t,a,b,c);
        a--; b--;
        if (t == 1) {
            tq.update(a, b, c);
        } else {
            ll ans = tq.query(a, b);
            writerLn(ans);
        }
    }
}

Compiler output:
a.cc: In function 'int main()':
a.cc:368:20: error: no matching function for call to 'reader(int&, int&)'
  368 |     int n,m; reader(n,m);
      |              ~~~~~~^~~~~
a.cc:354:34: note: candidate: 'template<class T, class S> void reader(T*, S*)'
  354 | template <class T, class S> void reader(T *x, S *y) { reader(x); reader(y); }
      |                                  ^~~~~~
a.cc:354:34: note:   template argument deduction/substitution failed:
a.cc:368:20: note:   mismatched types 'T*' and 'int'
  368 |     int n,m; reader(n,m);
      |              ~~~~~~^~~~~
a.cc:355:43: note: candidate: 'template<class T, class S, class U> void reader(T*, S*, U*)'
  355 | template <class T, class S, class U> void reader(T *x, S *y, U *z) { reader(x); reader(y); reader(z); }
      |                                           ^~~~~~
a.cc:355:43: note:   candidate expects 3 arguments, 2 provided
a.cc:356:52: note: candidate: 'template<class T, class S, class U, class V> void reader(T*, S*, U*, V*)'
  356 | template <class T, class S, class U, class V> void reader(T *x, S *y, U *z, V *w) { reader(x); reader(y); reader(z); reader(w); }
      |                                                    ^~~~~~
a.cc:356:52: note:   candidate expects 4 arguments, 2 provided
a.cc:351:6: note: candidate: 'void reader(int*)'
  351 | void reader(int *x) { int k, m = 0; *x = 0; for (;;) { mygc(k); if (k == '-') { m = 1; break; }if ('0' <= k&&k <= '9') { *x = k - '0'; break; } }for (;;) { mygc(k); if (k<'0' || k>'9')break; *x = (*x) * 10 + k - '0'; }if (m)(*x) = -(*x); }
      |      ^~~~~~
a.cc:351:6: note:   candidate expects 1 argument, 2 provided
a.cc:352:6: note: candidate: 'void reader(ll*)'
  352 | void reader(ll *x) { int k, m = 0; *x = 0; for (;;) { mygc(k); if (k == '-') { m = 1; break; }if ('0' <= k&&k <= '9') { *x = k - '0'; break; } }for (;;) { mygc(k); if (k<'0' || k>'9')break; *x = (*x) * 10 + k - '0'; }if (m)(*x) = -(*x); }
      |      ^~~~~~
a.cc:352:6: note:   candidate expects 1 argument, 2 provided
a.cc:353:5: note: candidate: 'int reader(char*)'
  353 | int reader(char c[]) { int i, s = 0; for (;;) { mygc(i); if (i != ' '&&i != '\n'&&i != '\r'&&i != '\t'&&i != EOF) break; }c[s++] = i; for (;;) { mygc(i); if (i == ' ' || i == '\n' || i == '\r' || i == '\t' || i == EOF) break; c[s++] = i; }c[s] = '\0'; return s; }
      |     ^~~~~~
a.cc:353:5: note:   candidate expects 1 argument, 2 provided
a.cc:370:21: error: no matching function for call to 'reader(__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type&)'
  370 |     FOR(i, n) reader(v[i]);
      |               ~~~~~~^~~~~~
a.cc:351:6: note: candidate: 'void reader(int*)' (near match)
  351 | void reader(int *x) { int k, m = 0; *x = 0; for (;;) { mygc(k); if (k == '-') { m = 1; break; }if ('0' <= k&&k <= '9') { *x = k - '0'; break; } }for (;;) { mygc(k); if (k<'0' || k>'9')break; *x = (*x) * 10 + k - '0'; }if (m)(*x) = -(*x); }
      |      ^~~~~~
a.cc:351:6: note:   conversion of argument 1 would be ill-formed:
a.cc:351:6: error: invalid conversion from '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} to 'int*' [-fpermissive]
  351 | void reader(int *x) { int k, m = 0; *x = 0; for (;;) { mygc(k); if (k == '-') { m = 1; break; }if ('0' <= k&&k <= '9') { *x = k - '0'; break; } }for (;;) { mygc(k); if (k<'0' || k>'9')break; *x = (*x) * 10 + k - '0'; }if (m)(*x) = -(*x); }
      |      ^~~~~~
      |      |
      |      __gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type {aka int}
a.cc:352:6: note: candidate: 'void reader(ll*)' (near match)
  352 | void reader(ll *x) { int k, m = 0; *x = 0; for (;;) { mygc(k); if (k == '-') { m = 1; break; }if ('0' <= k&&k <= '9') { *x = k - '0'; break; } }for (;;) { mygc(k); if (k<'0' || k>'9')break; *x = (*x) * 10 + k - '0'; }if (m)(*x) = -(*x); }
      |      ^~~~~~
a.cc:352:6: note:   conversion of argument 1 would be ill-formed:
a.cc:352:6: error: invalid conversion from '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} to 'll*' {aka 'long long int*'} [-fpermissive]
  352 | void reader(ll *x) { int k, m = 0; *x = 0; for (;;) { mygc(k); if (k == '-') { m = 1; break; }if ('0' <= k&&k <= '9') { *x = k - '0'; break; } }for (;;) { mygc(k); if (k<'0' || k>'9')break; *x = (*x) * 10 + k - '0'; }if (m)(*x) = -(*x); }
      |      ^~~~~~
      |      |
      |      __gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type {aka int}
a.cc:353:5: note: candidate: 'int reader(char*)' (near match)
  353 | int reader(char c[]) { int i, s = 0; for (;;) { mygc(i); if (i != ' '&&i != '\n'&&i != '\r'&&i != '\t'&&i != EOF) break; }c[s++] = i; for (;;) { mygc(i); if (i == ' ' || i == '\n' || i == '\r' || i == '\t' || i == EOF) break; c[s++] = i; }c[s] = '\0'; return s; }
      |     ^~~~~~
a.cc:353:5: note:   conversion of argument 1 would be ill-formed:
a.cc:353:5: error: invalid conversion from '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} to 'char*' [-fpermissive]
  353 | int reader(char c[]) { int i, s = 0; for (;;) { mygc(i); if (i != ' '&&i != '\n'&&i != '\r'&&i != '\t'&&i != EOF) break; }c[s++] = i; for (;;) { mygc(i); if (i == ' ' || i == '\n' || i == '\r' || i == '\t' || i == EOF) break; c[s++] = i; }c[s] = '\0'; return s; }
      |     ^~~~~~
      |     |
      |     __gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type {aka int}
a.cc:354:34: note: candidate: 'template<class T, class S> void reader(T*, S*)'
  354 | template <class T, class S> void reader(T *x, S *y) { reader(x); reader(y); }
      |                                  ^~~~~~
a.cc:354:34: note:   candidate expects 2 arguments, 1 provided
a.cc:355:43: note: candidate: 'template<class T, class S, class U> void reader(T*, S*, U*)'
  355 | template <class T, class S, class U> void reader(T *x, S *y, U *z) { reader(x); reader(y); reader(z); }
      |                                           ^~~~~~
a.cc:355:43: note:   candidate expects 3 arguments, 1 provided
a.cc:356:52: note: candidate: 'template<class T, class S, class U, class V> void reader(T*, S*, U*, V*)'
  356 | template <class T, class S, class U, class V> void reader(T *x, S *y, U *z, V *w) { reader(x); reader(y); reader(z); reader(w); }
      |                                                    ^~~~~~
a.cc:356:52: note:   candidate expects 4 arguments, 1 provided
a.cc:373:24: error: no matching function for call to 'reader(int&, int&)'
  373 |         int a,b; reader(a,b);
      |                  ~~~~~~^~~~~
a.cc:354:34: note: candidate: 'template<class T, class S> void reader(T*, S*)'
  354 | template <class T, class S> void reader(T *x, S *y) { reader(x); reader(y); }
      |                                  ^~~~~~
a.cc:354:34: note:   template argument deduction/substitution failed:
a.cc:373:24: note:   mismatched types 'T*' and 'int'
  373 |         int a,b; reader(a,b);
      |                  ~~~~~~^~~~~
a.cc:355:43: note: candidate: 'template<class T, class S, class U> void reader(T*, S*, U*)'
  355 | template <class T, class S, class U> void reader(T *x, S *y, U *z) { reader(x); reader(y); reader(z); }
      |                                           ^~~~~~
a.cc:355:43: note:   candidate expects 3 arguments, 2 provided
a.cc:356:52: note: candidate: 'template<class T, class S, class U, class V> void reader(T*, S*, U*, V*)'
  356 | template <class T, class S, class U, class V> void reader(T *x, S *y, U *z, V *w) { reader(x); reader(y); reader(z); reader(w); }
      |                                                    ^~~~~~
a.cc:356:52: note:   candidate expects 4 arguments, 2 provided
a.cc:351:6: note: candidate: 'void reader(int*)'
  351 | void reader(int *x) { int k, m = 0; *x = 0; for (;;) { mygc(k); if (k == '-') { m = 1; break; }if ('0' <= k&&k <= '9') { *x = k - '0'; break; } }for (;;) { mygc(k); if (k<'0' || k>'9')break; *x = (*x) * 10 + k - '0'; }if (m)(*x) = -(*x); }
      |      ^~~~~~
a.cc:351:6: note:   candidate expects 1 argument, 2 provided
a.cc:352:6: note: candidate: 'void reader(ll*)'
  352 | void reader(ll *x) { int k, m = 0; *x = 0; for (;;) { mygc(k); if (k == '-') { m = 1; break; }if ('0' <= k&&k <= '9') { *x = k - '0'; break; } }for (;;) { mygc(k); if (k<'0' || k>'9')break; *x = (*x) * 10 + k - '0'; }if (m)(*x) = -(*x); }
      |      ^~~~~~
a.cc:352:6: note:   candidate expects 1 argument, 2 provided
a.cc:353:5: note: candidate: 'int reader(char*)'
  353 | int reader(char c[]) { int i, s = 0; for (;;) { mygc(i); if (i != ' '&&i != '\n'&&i != '\r'&&i != '\t'&&i != EOF) break; }c[s++] = i; for (;;) { mygc(i); if (i == ' ' || i == '\n' || i == '\r' || i == '\t' || i == EOF) break; c[s++] = i; }c[s] = '\0'; return s; }
      |     ^~~~~~
a.cc:353:5: note:   candidate expects 1 argument, 2 provided
a.cc:382:22: error: 'reade' was not declared in this scope; did you mean 'reader'?
  382 |         int t,a,b,c; reade(t,a,b,c);
      |                      ^~~~~
      |                      reader