rt link

只过了特殊性质 C，但是手搓了十组左右的数据都没问题，求助万能的谷民，在线等，玄关

#include <cstdio>
#include <vector>
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
using namespace std;
int c[200005], d[200005], dep[200005], fa[200005][20], st[200005][20], pre[200005];
vector<pair<int, int>> g[200005];
void dfs(int x) {
    for (int i = 1; i < 20; i++)
        fa[x][i] = fa[fa[x][i - 1]][i - 1];
    dep[x] = dep[fa[x][0]] + 1;
    st[x][0] = c[x] - d[x] * 2;
    for (auto i: g[x])
        if (i.first != fa[x][0]) {
            fa[i.first][0] = x;
            d[i.first] = d[x] + i.second;
            dfs(i.first);
            st[x][0] = max(st[x][0], st[i.first][0]);
        }
}
void calc(int x) {
    pre[x] = max(pre[x], pre[fa[x][0]]);
    for (int i = 1; i < 20; i++)
        st[x][i] = max(st[x][i - 1], st[fa[x][i - 1]][i - 1]);
    for (auto i: g[x])
        if (i.first != fa[x][0])
            calc(i.first);
}
int lca(int x, int y) {
    if (dep[x] < dep[y])
        swap(x, y);
    for (int i = dep[x] - dep[y], j = 0; i; i >>= 1, j++)
        if (i & 1)
            x = fa[x][i];
    if (x == y)
        return x;
    for (int i = 19; i >= 0; i--)
        if (fa[x][i] != fa[y][i]) {
            x = fa[x][i];
            y = fa[y][i];
        }
    return fa[x][0];
}
signed main() {
    int n, q;
    scanf("%lld%lld", &n, &q);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &c[i]);
    for (int i = 1; i < n; i++) {
        int u, v, w;
        scanf("%lld%lld%lld", &u, &v, &w);
        g[u].emplace_back(make_pair(v, w));
        g[v].emplace_back(make_pair(u, w));
    }
    pre[0] = -inf;
    for (int i = 0; i < 20; i++)
        st[0][i] = -inf;
    dfs(1);
    for (int i = 1; i <= n; i++) {
        pre[i] = st[i][0] + d[i] * 4;
        st[i][0] += d[i] * 2;
    }
    calc(1);
    while (q--) {
        int x, y, ans = -inf;
        scanf("%lld%lld", &x, &y);
        int u = lca(x, y), ret = c[x] + c[y] - d[x] - d[y];
        for (int i = dep[x] - dep[u], j = 0; i; i >>= 1, j++)
            if (i & 1) {
                ans = max(ans, st[x][j]);
                x = fa[x][j];
            }
        for (int i = dep[y] - dep[u], j = 0; i; i >>= 1, j++)
            if (i & 1) {
                ans = max(ans, st[y][j]);
                y = fa[y][j];
            }
        printf("%lld\n", ret + max(ans + d[u] * 2, pre[u]));
    }
    return 0;
}

还有一个比较玄学的就是改成下面这样直接 0 分，要是有大佬的话能不能解答一下：

void dfs(int x) {
    for (int i = 1; i < 20; i++)
        fa[x][i] = fa[fa[x][i - 1]][i - 1];
    st[x][0] = c[x] - d[x] * 2;
    for (auto i: g[x])
        if (i.first != fa[x][0]) {
            fa[i.first][0] = x;
            d[i.first] = d[x] + i.second;
            dep[i.first] = dep[x] + 1;
            dfs(i.first);
            st[x][0] = max(st[x][0], st[i.first][0]);
        }
}