也许是常数问题，第 7 个点本地 0.6s。

#include <bits/stdc++.h>

using namespace std;

inline int read() {
  int s = 0, w = 1;
  char c = getchar();
  while (!isdigit(c)) {
    w = c == '-' ? -w : w;
    c = getchar();
  }
  while (isdigit(c)) {
    s = s * 10 + c - 48;
    c = getchar();
  }
  return s * w;
}

const int inf = 1e9;
const int maxN = 1e5 + 7;

int n, m;
int a[maxN];
vector<int> E[maxN];

struct matrix {
  int a[3][3], n, m;
  matrix(int _n = 0, int _m = 0) {
    memset(a, ~0x3f, sizeof(a));
    n = _n, m = _m;
  }
  int * operator [] (int x) {
    return a[x];
  }
  friend matrix operator * (matrix A, matrix B) {
    matrix C(A.n, B.m);
    for (int i = 1; i <= A.n; ++i)
      for (int k = 1; k <= A.m; ++k)
        for (int j = 1; j <= B.m; ++j)
          C[i][j] = max(C[i][j], A[i][k] + B[k][j]);
    return C;
  }
 // friend matrix operator * (matrix A, matrix B) {
 //   matrix C(A.n, B.m);
 //   for (int i = 1; i <= A.n; ++i)
 //     for (int j = 1; j <= B.m; ++j)
 //       for (int k = 1; k <= A.m; ++k)
 //         C[i][j] = max(C[i][j], A[i][k] + B[k][j]);
 //   return C;
 // }

  //void put() {
  //  cerr << n << ' ' << m << '\n';
  //  for (int i = 1; i <= n; i++, cerr << '\n')
  //    for (int j = 1; j <= m; j++)
  //      cerr << a[i][j] << ' ';
  //}
} Rr(2, 2);

#define end qwpjmdkjfdh
int dfn[maxN], rk[maxN], tot;
int siz[maxN], son[maxN], fa[maxN], top[maxN];
int end[maxN];
void dfs1(int x, int f) {
  fa[x] = f;
  siz[x] = 1;
  for (auto to : E[x])
    if (to != f) {
      dfs1(to, x);
      siz[x] += siz[to];
      if (siz[to] > siz[son[x]])
        son[x] = to;
    }
}
void dfs2(int x, int tp) {
  top[x] = tp;
  dfn[x] = ++tot;
  rk[tot] = x;
  end[x] = x;
  if (!son[x]) return;
  dfs2(son[x], tp);
  end[x] = end[son[x]];
  for (auto to : E[x])
    if (to != fa[x] && to != son[x])
      dfs2(to, to);
}
matrix V[maxN];
int f[maxN][2], g[maxN][2];
void dfs(int x) {
  f[x][0] = 0, f[x][1] = a[x];
  g[x][1] = a[x];
  for (auto to : E[x])
    if (to != fa[x]) {
      dfs(to);
      if (to != son[x]) {
        g[x][0] += max(f[to][0], f[to][1]);
        g[x][1] += f[to][0];
      }
    }
  f[x][0] = g[x][0] + max(f[son[x]][0], f[son[x]][1]);
  f[x][1] = g[x][1] + f[son[x]][0];
  V[x] = matrix(2, 2);
  V[x][1][1] = g[x][0];
  V[x][1][2] = g[x][0];
  V[x][2][1] = g[x][1];
  V[x][2][2] = -inf;
}

matrix t[maxN * 4];
#define ls (p << 1)
#define rs (p << 1 | 1)
inline void upd(int p) {
  t[p] = t[ls] * t[rs];
}
void build(int l, int r, int p) {
  t[p] = matrix(2, 2);
  if (l == r) {
    t[p] = V[rk[l]];
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, ls), build(mid + 1, r, rs);
  upd(p);
}
void change(int K, int p, int l, int r) {
  if (l == r) return t[p] = V[rk[l]], void();
  int mid = (l + r) >> 1;
  K <= mid ? change(K, ls, l, mid) : change(K, rs, mid + 1, r);
  upd(p);
}
matrix ask(int L, int R, int p, int l, int r) {   
  if (L <= l && r <= R) return t[p];
  int mid = (l + r) >> 1;
  matrix res = Rr;
  if (L <= mid)
    res = res * ask(L, R, ls, l, mid);
  if (R > mid)
    res = res * ask(L, R, rs, mid + 1, r);
  return res;
}

void modify(int x, int v) {
  V[x][2][1] += -a[x] + v;
  a[x] = v;
  while (x != 0) {
    int f = fa[top[x]];
    auto tmp = ask(dfn[top[x]], dfn[end[x]], 1, 1, n);
    V[f][1][1] -= max(tmp[1][1], tmp[2][1]);
    V[f][1][2] = V[x][1][1];
    V[f][2][1] -= tmp[1][1];
    change(dfn[x], 1, 1, n);
    tmp = ask(dfn[top[x]], dfn[end[x]], 1, 1, n);
    V[f][1][1] += max(tmp[1][1], tmp[2][1]);
    V[f][1][2] = V[f][1][1];
    V[f][2][1] += tmp[1][1];
    x = f;
  }
}

int main() {
  //freopen("P4719_7.in", "r", stdin);
  //freopen("out.out", "w", stdout);

  Rr[1][1] = Rr[2][2] = 0;

  n = read(), m = read();
  for (int i = 1; i <= n; i++)
    a[i] = read();

  for (int i = 1; i < n; i++) {
    int u, v;
    u = read(), v = read();
    E[u].emplace_back(v);
    E[v].emplace_back(u);
  }
  dfs1(1, 0);
  dfs2(1, 1);
  dfs(1);
  
  build(1, n, 1);

  while (m--) {
    int x, y;
    x = read(), y = read();
    modify(x, y);
    matrix res = ask(dfn[1], dfn[end[1]], 1, 1, n);
    printf("%d\n", max(res[1][1], res[2][1]));
  }
}