倍增做法求调（悬赏30）

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'

inline ll read(){
    ll res = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        res = res * 10 + c - '0';
        c = getchar();
    }
    return res * f;
}

const int N = 300010;
const ll INF = 0x3f3f3f3f3f3f3f3f;

ll c[N];
ll h[N], ne[N * 2], e[N * 2], w[N * 2], idx;
void add(ll a, ll b, ll c){
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
    return;
}

ll f[N][20], max_sp[N], cost[N][20], max_down[N][20], deep[N], max_up[N];

void dfs(ll u, ll fa, ll maxx){
    f[u][0] = fa;
    deep[u] = deep[fa] + 1;
    max_sp[u] = c[u];
    max_up[u] = max(maxx, c[u]);
    for(int i = 1; i <= 17; i ++){
        f[u][i] = f[f[u][i - 1]][i - 1];
        cost[u][i] = cost[u][i - 1] + cost[f[u][i - 1]][i - 1];
    }
    for(int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        if(j == fa)continue;
        cost[j][0] = w[i];
        dfs(j, u, max_up[u] - 2 * w[i]);
        max_sp[u] = max(max_sp[u], max_sp[j] - 2 * w[i]);
    }
    return;
}

void dfss(ll u, ll fa){
    max_down[u][0] = max(max_sp[u], max_sp[fa]);
    for(int i = 1; i <= 17; i ++){
        max_down[u][i] = max(max_down[u][i - 1], max_down[f[u][i - 1]][i - 1]);
    }
    for(int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        if(j == fa)continue;
        dfss(j, u);
    }
    return;
}

ll ans(ll u, ll v){
    ll res = c[u] + c[v];
    ll maxx = max(max_sp[u], max_sp[v]);
    if(deep[u] < deep[v])swap(u, v);
    for(int i = 17; i >= 0; i --){
        if(deep[f[u][i]] >= deep[v]){
            res -= cost[u][i];
            maxx = max(maxx, max_down[u][i]);
            u = f[u][i];
        }
    }
    if(u == v){
        maxx = max(maxx, max_up[u]);
        maxx = max(maxx, max_sp[u]);
        return res + maxx;
    }
    for(int i =17; i >= 0; i --){
        if(f[u][i] != f[v][i]){
            res -= cost[u][i];
            res -= cost[v][i];
            maxx = max(maxx, max_up[u]);
            maxx = max(maxx, max_up[v]);
            maxx = max(maxx, max_down[u][i]);
            maxx = max(maxx, max_down[v][i]);
            u = f[u][i];
            v = f[v][i];
        }
    }
    res -= cost[u][0];
    res -= cost[v][0];
    ll LCA = f[u][0];
    maxx = max(maxx, max_up[LCA]);
    maxx = max(maxx, max_down[u][0]);
    maxx = max(maxx, max_down[v][0]);
    return res + maxx;
}

signed main(){
    memset(h, -1, sizeof h);
    ll n = read(), q = read();
    for(int i = 1; i <= n; i ++){
        c[i] = read();
    }
    for(int i = 1; i < n; i ++){
        ll u = read(), v = read(), W = read();
        add(u, v, W), add(v, u, W);
    }
    dfs(1, 0, 0);
    dfss(1, 0);
    while(q --){
        ll u = read(), v = read();
        cout << ans(u, v) << endl;
    }    
    return 0;
}