代码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 1e+5 + 5;
const int inf = 0x3f3f3f3f;

//------ GRAPH STARTS----------
struct edge {
  int to, nxt;
}e[maxn << 1];
int n, m, lnk[maxn], ptr, siz[maxn], mxson[maxn];
int rev[maxn], f[maxn], top[maxn], bot[maxn];
int dfn[maxn], cnt;
ll dp[maxn][2], v[maxn], sum;

inline void InitNewEdge(int bgn, int end) {
  e[++ptr] = (edge){end, lnk[bgn]};
  lnk[bgn] = ptr;
}
inline int ReadInt() {
  register int x = 0, f = 0, c = getchar();
  while (!isdigit(c)) {
    if (c == '-') f = 1;
    c = getchar();
  }
  while (isdigit(c)) {
    x = x * 10 + (c ^ 48);
    c = getchar();
  }
  return f ? -x : x;
}
void dfs(int x, int fa) {
  siz[x] = 1;
  f[x] = fa;
  dp[x][1] = v[x];
  for (int p = lnk[x]; p; p = e[p].nxt) {
    int y = e[p].to;
    if (y == fa) continue;
    dfs(y, x);
    dp[x][1] += dp[y][0];
    dp[x][0] += max(dp[y][1], dp[y][0]);
    siz[x] += siz[y];
    if (siz[y] > siz[mxson[x]]) mxson[x] = y;
  }
}
void dfs2(int x, int init) {
  top[x] = init;
  dfn[x] = ++cnt; rev[cnt] = x;
  if (!mxson[x]) {
    bot[x] = x;
    return;
  }
  dfs2(mxson[x], init); bot[x] = bot[mxson[x]];
  for (int p = lnk[x]; p; p = e[p].nxt) {
    int y = e[p].to;
    if (y == f[x] || y == mxson[x]) continue;
    dfs2(y, y);
  }
}
//-------GRAPH ENDS------------

//-------MATRIX STARTS---------
struct matrix {
  ll a[2][2];
  matrix(const ll &arg_1 = 0, const ll &arg_2 = 0,
         const ll &arg_3 = 0, const ll &arg_4 = 0) {
    a[0][0] = arg_1;
    a[0][1] = arg_2;
    a[1][0] = arg_3;
    a[1][1] = arg_4;
  }
  ll* operator[](int x) {
    return a[x];
  }
  inline matrix operator*(matrix rhs) {
    matrix ret;
    ret[0][0] = max(a[0][1] + rhs[1][0], a[0][0] + rhs[0][0]);
    ret[0][1] = max(a[0][1] + rhs[1][1], a[0][0] + rhs[0][1]);
    ret[1][0] = max(a[1][0] + rhs[0][0], a[1][1] + rhs[1][0]);
    ret[1][1] = max(a[1][1] + rhs[1][1], a[1][0] + rhs[0][1]);
    return ret;
  }
};
matrix node[maxn << 2], pt[maxn];
void build(int cur, int l, int r) {
  if (l == r) {
    int R = rev[l];
    ll f0 = 0, f1 = v[R];
    for (int p = lnk[R]; p; p = e[p].nxt) {
      int y = e[p].to;
      if (y == f[R] || y == mxson[R]) continue;
      f0 += max(dp[y][1], dp[y][0]);
      f1 += dp[y][0];
    }
    node[cur] = pt[l] = matrix(f0, f0, f1, -inf);
    return;
  }
  int mid = (l + r) >> 1;
  build(cur << 1, l, mid);
  build(cur << 1|1, mid + 1, r);
  node[cur] = node[cur << 1] * node[cur << 1|1];
}
void modify(int cur, int l, int r, int p) {
  if (l == r) {
    node[cur] = pt[l];
    return;
  }
  int mid = (l + r) >> 1;
  if (p <= mid) modify(cur << 1, l, mid, p);
  else modify(cur << 1|1, mid + 1, r, p);
  node[cur] = node[cur << 1] * node[cur << 1|1];
}
matrix query(int cur, int l, int r, int L, int R) {
  if (L == l && r <= R) return node[cur];
  int mid = (l + r) >> 1;
  if (R <= mid) return query(cur << 1, l, mid, L, R);
  else if (L > mid) return query(cur << 1|1, mid + 1, r, L, R);
  else return query(cur << 1, l, mid, L, mid) * 
              query(cur << 1|1, mid + 1, r, mid + 1, R);
}
//-------MATRIX ENDS-----------

//------SOLUTION STARTS--------
matrix GetChain(int x) {
  return query(1, 1, n, dfn[top[x]], dfn[bot[x]]);
}
void modify(int x, int val) {
  pt[dfn[x]][1][0] += val - v[x]; 
  v[x] = val;
  while (x) {
    matrix Origin = GetChain(top[x]);
    modify(1, 1, n, dfn[x]);
    matrix New = GetChain(top[x]);
    x = f[top[x]];
    if (!x) break;
    pt[dfn[x]][0][0] += max(New[0][0], New[1][0]) - 
                        max(Origin[0][0], Origin[1][0]);
    pt[dfn[x]][0][1] = pt[dfn[x]][0][0];
    pt[dfn[x]][1][0] += New[0][0] - Origin[0][0];
  }
}
//--------SOLUTION ENDS--------

inline void solve(int u, int x, int r, int y) {
  if ((f[u] == r || f[r] == u) && !x && !y) {
    puts("-1");
    return;
  }
  int memx = v[u], memy = v[r];
  if (!x) modify(u, inf);
  else modify(u, -inf);
  if (!y) modify(r, inf);
  else modify(r, -inf);
  matrix ans = GetChain(1);
  ll GDS = max(ans[0][0], ans[1][0]);
  if (!x) GDS -= inf, GDS += memx;
  if (!y) GDS -= inf, GDS += memy;
  GDS = sum - GDS;
  printf("%lld\n", GDS);
  modify(u, memx);
  modify(r, memy);
}

#define VertexSum n
#define OptionSum m

int main(int argc, char const *argv[]) {
  static char Type[5];
  VertexSum = ReadInt(); 
  OptionSum = ReadInt();
  scanf("%s", Type);
  for (int i = 1; i <= VertexSum; ++i) 
    v[i] = ReadInt(), sum += v[i];
  typedef int Vertex_t;
  Vertex_t VertexFrom, VertexTo;
  for (int i = 1; i < VertexSum; ++i) {
    VertexFrom = ReadInt();
    VertexTo = ReadInt();
    InitNewEdge(VertexFrom, VertexTo);
    InitNewEdge(VertexTo, VertexFrom);
  }
  dfs(1, 0);
  dfs2(1, 1);
  build(1, 1, n);
  int x, y;
  while (m--) {
    VertexFrom = ReadInt(); x = ReadInt();
    VertexTo = ReadInt(); y = ReadInt();
    solve(VertexFrom, x,
          VertexTo, y);
    /*modify(x, y);
    matrix ans = GetChain(1);
    printf("%lld\n", max(ans[0][0], ans[1][0]));*/

  }
  return 0;
}

评测结果