WA 28pts 求条/hack数据玄红名小号一关

#include <bits/stdc++.h>

using namespace std;

const long long N = 2e5 + 5;

long long n, q, c[N], dep[N], f[N][22], dp[N][22], dis[N], s[N], sum[N], tmp[N];

struct S {
  long long x, w;
};

vector<S> v[N];

void Dfs(long long x, long long fa, long long mx) {
  s[x] = max(c[x], mx - (2ll * dis[x]));
  f[x][1] = fa, dep[x] = dep[fa] + 1;
  tmp[x] = c[x] - (2ll * dis[x]);
  for (long long i = 0; i < v[x].size(); i++) {
    long long nx = v[x][i].x;
    if (nx == fa) {
      continue;
    }
    dis[nx] = dis[x] + v[x][i].w;
    Dfs(nx, x, max(mx, c[x] + (2 * dis[x])));
    tmp[x] = max(tmp[x], tmp[nx]);
  } 
  sum[x] = tmp[x] + (2 * dis[x]);
  dp[x][0] = sum[x];
}

void init() {
  for (long long i = 1; i <= n; i++) {
    dp[i][1] = max(dp[i][0], dp[f[i][1]][0]);
  }
  for (long long j = 2; j <= 20; j++) {
    for (long long i = 1; i <= n; i++) {
      f[i][j] = f[f[i][j - 1]][j - 1];
      dp[i][j] = max(dp[i][j - 1], dp[f[i][j - 1]][j - 1]);
    }
  }
}

long long lca(long long x, long long y) {
  if (dep[x] < dep[y]) {
    swap(x, y);
  }
  long long sum = -(dis[x] + dis[y]);
  long long ans = max(dp[x][0], dp[y][0]);
  for (long long i = 20; i >= 1; i--) {
    if (dep[f[x][i]] >= dep[y]) {
      ans = max(ans, dp[x][i]);
      x = f[x][i];
    }
  }
  for (long long i = 20; i >= 1; i--) {
    if (f[x][i] != f[y][i]) {
      ans = max(ans, max(dp[x][i], dp[y][i]));
      x = f[x][i], y = f[y][i];
    }
  }
  if (x != y) {
    ans = max(ans, max(dp[x][1], dp[y][1]));
    x = f[x][1], y = f[y][1];
  }
  sum += 2ll * dis[x];
  ans = max (ans, max(s[x], dp[x][0]));
  return ans + sum;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n >> q;
  for (long long i = 1; i <= n; i++) {
    cin >> c[i];
  }
  for (long long i = 1, x, y, w; i < n; i++) {
    cin >> x >> y >> w;
    v[x].push_back({y, w}), v[y].push_back({x, w});
  }
  Dfs(1, 0, 0), init();
  for (long long x, y; q--;) {
    cin >> x >> y;
    cout << lca(x, y) + c[x] + c[y] << "\n";
  }
  return 0;
}