代码

#include <cstdio>
#include <cctype>
#include <cstring>
#include <vector>
#include <algorithm>
#ifdef ONLINE_JUDGE
#define freopen(a, b, c)
#endif

typedef long long int ll;

namespace IPT {

const int L = 1 << 21;
char buf[L], *front=buf, *end=buf;
char GetChar() {
  if (front == end) end = buf + fread(front = buf, 1, L, stdin);
  return (front == end) ? -1 : *(front++);
}
template <typename T>
inline void qr(T &x) {
  char ch = GetChar(), lst = 0; x = 0;
  while (!isdigit(ch)) lst = ch, ch = GetChar();
  while (isdigit(ch)) x = x * 10 + (ch ^ 48), ch = GetChar();
  if (lst == '-') x = -x;
}
template <typename T>
void qra(T *const __ary, int __n) {
  for (int i = 0; i < __n; ++i) qr(__ary[i]);
}
template <typename T>
int qrs(T *p) {
  T *beg = p;
  do *p = GetChar(); while (!isalnum(*p));
  do *(++p) = GetChar(); while (isalnum(*p));
  *p = 0;
  return p - beg;
}
template <typename T>
void qrdb(T &x) {
  char ch = GetChar(), lst = 0; x = 0;
  while (!isdigit(ch)) lst = ch, ch = GetChar();
  while (isdigit(ch)) { x = x * 10 + (ch - '0'); ch = GetChar(); }
  if (ch == '.') {
    ch = GetChar();
    for (double t = 0.1; isdigit(ch); t *= 0.1) {
      x += (t * (ch - '0'));
      ch = GetChar();
    }
  }
  if (lst == '-') x = -x;
}

} // namespace IPT

namespace OPT {

const int L = 30;
char buf[L];

template <typename T>
inline void qw(T x, const char aft = 0) {
  if (x < 0) { x = -x, putchar('-'); }
  int top = 0;
  do { buf[++top] = static_cast<char>(x % 10 + '0'); } while (x /= 10);
  while (top) putchar(buf[top--]);
  if (aft) putchar(aft);
}
template <typename T>
void qwa(T *const __ary, int __n, const char e1, const char e2) {
  int __dn = __n - 1;
  for (int i = 0; i < __dn; ++i) qw(__ary[i], e1);
  qw(__ary[__dn], e2);
}
template <typename T>
void qws(T *p, const int __n, const char ed) {
  for (int i = 0; i < __n; ++i) putchar(p[i]);
  if (ed) putchar(ed);
}
template <typename T>
void qws(T *p, const char ed) {
  while (*p) putchar(*p++);
  if(ed) putchar(ed);
}

} // namespace OPT

using IPT::qr;
using IPT::qra;
using IPT::qrs;
using IPT::qrdb;
using OPT::qw;
using OPT::qwa;
using OPT::qws;

namespace Fusu { void Main(); }

int main() {
  freopen("1.in", "r", stdin);
  Fusu::Main();
  return 0;
}

namespace Fusu {

const int maxn = 100005;
const ll INF = 0x3f3f3f3f3f3f3f3fll;

int n, q;
char yzyovozay[maxn];
ll a[maxn], g[maxn][2], f[maxn][2];
std::vector<int> e[maxn];

struct Mat {
  ll mt[2][2];

  Mat(const int x = 0) {
    mt[0][0] = INF;
    mt[1][0] = g[x][0];
    mt[1][1] = g[x][1];
    mt[0][1] = g[x][1];
  }

  Mat operator*(const Mat &o) const {
    Mat ret;
    for (int i = 0; i < 2; ++i) {
      for (int j = 0; j < 2; ++j) {
        ret.mt[i][j] = INF;
        for (int k = 0; k < 2; ++k) {
          ret.mt[i][j] = std::min(ret.mt[i][j], mt[i][k] + o.mt[k][j]);
        }
      }
    }
    return ret;
  }
};

int rmp[maxn];
struct Node {
  int l, r;
  Node *ls, *rs;
  Mat v;

  inline void pushup() { v = rs->v * ls->v; }

  void upd(const int p) {
    if ((p < l) || (p > r)) return;
    if (l == r) {
      v = Mat(rmp[l]);
    } else {
      ls->upd(p);
      rs->upd(p);
      pushup();
    }
  }
};
Node *rot[maxn], Mem[maxn << 1], *pool = Mem;
Node *New(const int l, const int r) {
  auto u = pool++;
  if ((u->l = l) != (u->r = r)) {
    int m = (l + r) >> 1;
    u->ls = New(l, m);
    u->rs = New(m + 1, r);
    u->pushup();
  } else {
    u->v = Mat(rmp[l]);
  }
  return u;
}

void dfs(const int u);
void dfs(const int u, const int tp);
void upd(int u);

void Main() {
  qr(n); qr(q); qrs(yzyovozay);
  qra(a + 1, n);
  g[0][0] = g[0][1] = INF;
  for (int u, v, i = 1; i < n; ++i) {
    qr(u); qr(v);
    e[u].push_back(v);
    e[v].push_back(u);
  }
  dfs(1);
  dfs(1, 1);
  for (int u, v, x, y; q; --q) {
    qr(u); qr(x); qr(v); qr(y);
    x ^= 1; y ^= 1;
    ll i = g[u][x], j = g[v][y];
    g[u][x] = INF;
    upd(u);
    g[v][y] = INF;
    upd(v);
    auto m = rot[1]->v;
    ll k = std::min({m.mt[0][0], m.mt[0][1], m.mt[1][0], m.mt[1][1]});
    if (k == INF) k = -1;
    qw(k, '\n');
    g[u][x] = i;
    upd(u);
    g[v][y] = j;
    upd(v);
  }
}

int wson[maxn], sz[maxn], fa[maxn];
void dfs(const int u) {
  sz[u] = 1;
  for (auto v : e[u]) if (sz[v] == 0) {
    dfs(v);
    fa[v] = u;
    sz[u] += sz[v];
    if (sz[v] > sz[wson[u]]) wson[u] = v;
  }
}

int vistime;
int dfn[maxn], rid[maxn], top[maxn];
void dfs(const int u, const int tp) {
  rmp[rid[top[u] = tp] = dfn[u] = ++vistime] = u;
  if (wson[u]) {
    dfs(wson[u], tp);
  }
  g[u][1] = a[u];
  for (auto v : e[u]) if (dfn[v] == 0) {
    dfs(v, v);
    g[u][0] += f[v][1];
    g[u][1] += std::min(f[v][1], f[v][0]);
  }
  f[u][0] = g[u][0] + f[wson[u]][1];
  f[u][1] = g[u][1] + std::min(f[wson[u]][1], f[wson[u]][0]);
  if (u == tp) {
    rot[u] = New(dfn[u], rid[u]);
  }
}

void upd(int u) {
  while (u) {
    int v = top[u], w = fa[v];
    auto m = rot[v]->v;
    ll f0 = std::min(m.mt[0][0], m.mt[1][0]), f1 = std::min(m.mt[0][1], m.mt[1][1]);
    ll g1 = std::min(f0, f1), g0 = f1;
    g[w][0] -= g0; g[w][1] -= g1;
    rot[v]->upd(dfn[u]);
    m = rot[v]->v;
    f0 = std::min(m.mt[0][0], m.mt[1][0]), f1 = std::min(m.mt[0][1], m.mt[1][1]);
    g1 = std::min(f0, f1), g0 = f1;
    g[w][0] += g0; g[w][1] += g1;
    u = w;
  }
}

} // namespace Fusu

评测结果