Language: C++

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007

struct HLDecomposition {
  vector<vector<int> > G;
  vector<int> vid, head, heavy, parent, depth, inv;
  HLDecomposition(int n) :
    G(n), vid(n, -1), head(n), heavy(n, -1), parent(n), depth(n), inv(n) {}

  void add_edge(int x, int y) {
    G[x].pb(y);
    G[y].pb(x);
  }

  void build() {
    dfs(0, -1);
    bfs();
  }

  int dfs(int x, int p) {
    parent[x] = p;
    int sub = 1, max_sub = 0;
    for (int t : G[x]) {
      if (t == p) continue;
      depth[t] = depth[x]+1;
      int sub_t = dfs(t, x);
      sub += sub_t;
      if (max_sub < sub_t) max_sub = sub_t, heavy[x] = t;
    }
    return sub;
  }

  void bfs() {
    int k = 0;
    queue<int> q;
    q.push(0);
    while (!q.empty()) {
      int h = q.front(); q.pop();
      for (int i=h; i!=-1; i=heavy[i]) {
        vid[i] = k++;
        inv[vid[i]] = i;
        head[i] = h;
        for (int j : G[i]) {
          if (j == parent[i] || j == heavy[i]) continue;
          q.push(j);
        }
      }
    }
  }

  void for_each(int u, int v, function<void(int, int, int)> f) {
    if (vid[u] > vid[v]) {
      f(max(vid[head[u]], vid[v]), vid[u], 1);
      if (head[u] != head[v]) for_each(parent[head[u]], v, f);
    }
    else {
      if (head[u] != head[v]) for_each(u, parent[head[v]], f);
      f(max(vid[head[v]], vid[u]), vid[v], 0);
    }
  }
};

struct Node {
  long long l, r, m, sum;
  Node() : l(0), r(0), m(-INF), sum(0) {}
  Node(long long l, long long r, long long m, long long s) :
    l(l), r(r), m(m), sum(s) {}
};
Node op(Node a, Node b) {
  if (a.m == -INF) return b;
  if (b.m == -INF) return a;
  return Node(
    max(a.l, a.sum + b.l),
    max(b.r, b.sum + a.r),
    max({a.m, b.m, a.r + b.l}),
    a.sum + b.sum
  );
}

#define MAX_N (1<<18)
Node seg[MAX_N*2-1];
int lazy[MAX_N*2-1];

void setLazy(int k, int v, int size) {
  lazy[k] = v;
  long long u = v;
  if (v >= 0) u = 1LL*size*v;
  seg[k] = Node(u, u, u, 1LL*size*v);
}

void push(int k, int size) {
  if (lazy[k] == -1) return;
  setLazy(k*2+1, lazy[k], size/2);
  setLazy(k*2+2, lazy[k], size/2);
  lazy[k] = -1;
}

Node query(int a, int b, int k=0, int l=0, int r=MAX_N) {
  if (r <= a || b <= l) return Node();
  if (a <= l && r <= b) return seg[k];
  push(k, r-l);
  return op(
    query(a, b, k*2+1, l, (l+r)/2),
    query(a, b, k*2+2, (l+r)/2, r));
}

void fill(int a, int b, int val, int k=0, int l=0, int r=MAX_N) {
  if (r <= a || b <= l) return;
  if (a <= l && r <= b) {
    setLazy(k, val, r-l);
    return;
  }
  push(k, r-l);
  fill(a, b, val, k*2+1, l, (l+r)/2);
  fill(a, b, val, k*2+2, (l+r)/2, r);
  seg[k] = op(seg[k*2+1], seg[k*2+2]);
}

int N, Q;
int W[200000];

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> N >> Q;
  HLDecomposition hld(N);
  rep(i, MAX_N*2-1) lazy[i] = -1;
  rep(i, N) cin >> W[i];
  rep(i, N-1) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    hld.add_edge(u, v);
  }
  hld.build();
  rep(i, N) {
    hld.for_each(i, i, [&](int l, int r, int d) {
      fill(l, r+1, W[i]);
    });
  }

  rep(_, Q) {
    int t, x, y, z;
    cin >> t >> x >> y >> z;
    x--, y--;
    if (t == 1) {
      // update [x, y] -> z
      hld.for_each(x, y, [&](int l, int r, int d) {
        fill(l, r+1, z);
      });
    }
    else {
      // query [x, y]
      Node node;
      hld.for_each(x, y, [&](int l, int r, int d) {
        Node t = query(l, r+1);
        if (d == 1) swap(t.l, t.r);
        node = op(node, t);
      });
      cout << node.m << "\n";
    }
  }
  return 0;
}

Compiler output:
a.cc:74:31: error: 'function' has not been declared
   74 |   void for_each(int u, int v, function<void(int, int, int)> f) {
      |                               ^~~~~~~~
a.cc:74:39: error: expected ',' or '...' before '<' token
   74 |   void for_each(int u, int v, function<void(int, int, int)> f) {
      |                                       ^
a.cc: In member function 'void HLDecomposition::for_each(int, int, int)':
a.cc:76:7: error: 'f' was not declared in this scope
   76 |       f(max(vid[head[u]], vid[v]), vid[u], 1);
      |       ^
a.cc:80:60: error: 'f' was not declared in this scope
   80 |       if (head[u] != head[v]) for_each(u, parent[head[v]], f);
      |                                                            ^
a.cc:81:7: error: 'f' was not declared in this scope
   81 |       f(max(vid[head[v]], vid[u]), vid[v], 0);
      |       ^
a.cc: In function 'int main()':
a.cc:159:24: error: cannot convert 'main()::<lambda(int, int, int)>' to 'int'
  159 |     hld.for_each(i, i, [&](int l, int r, int d) {
      |                        ^~~~~~~~~~~~~~~~~~~~~~~~~~
      |                        |
      |                        main()::<lambda(int, int, int)>
  160 |       fill(l, r+1, W[i]);
      |       ~~~~~~~~~~~~~~~~~~~
  161 |     });
      |     ~                   
a.cc:74:31: note:   initializing argument 3 of 'void HLDecomposition::for_each(int, int, int)'
   74 |   void for_each(int u, int v, function<void(int, int, int)> f) {
      |                               ^~~~~~~~
a.cc:170:26: error: cannot convert 'main()::<lambda(int, int, int)>' to 'int'
  170 |       hld.for_each(x, y, [&](int l, int r, int d) {
      |                          ^~~~~~~~~~~~~~~~~~~~~~~~~~
      |                          |
      |                          main()::<lambda(int, int, int)>
  171 |         fill(l, r+1, z);
      |         ~~~~~~~~~~~~~~~~  
  172 |       });
      |       ~                   
a.cc:74:31: note:   initializing argument 3 of 'void HLDecomposition::for_each(int, int, int)'
   74 |   void for_each(int u, int v, function<void(int, int, int)> f) {
      |                               ^~~~~~~~
a.cc:177:26: error: cannot convert 'main()::<lambda(int, int, int)>' to 'int'
  177 |       hld.for_each(x, y, [&](int l, int r, int d) {
      |                          ^~~~~~~~~~~~~~~~~~~~~~~~~~
      |                          |
      |                          main()::<lambda(int, int, int)>
  178 |         Node t = query(l, r+1);
      |         ~~~~~~~~~~~~~~~~~~~~~~~
  179 |         if (d == 1) swap(t.l, t.r);
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~
  180 |         node = op(node, t);
      |         ~~~~~~~~~~~~~~~~~~~
  181 |       });
      |       ~                   
a.cc:74:31: note:   initializing argument 3 of 'void HLDecomposition::for_each(int, int, int)'
   74 |   void for_each(int u, int v, function<void(int, int, int)> f) {
      |                               ^~~~~~~~