求助卡常

//P12511
#include <bits/stdc++.h>
using namespace std;

/*
对第二棵树进行树分块
链拆根链

第二棵树 B 个单点查 + 1 个关键点根链查
计算第一棵树每一条根链 <-> 第二棵树关键点根链 n^2/B 个对应关系
根链加/单点查 第一棵树 dfn 序分块后 O(B)-O(1)
*/

const int N = 2e5 + 10, B = 300;
typedef unsigned long long ll;
int n, m;
ll a[N];

struct tree{
    vector<int> g[N];
    int anc[18][N], dep[N];
    int dfn[N], siz[N];
    void dfs(int x, int fa){
        dfn[x] = ++ dfn[0];
        siz[x] = 1;
        anc[0][x] = fa;
        dep[x] = dep[fa] + 1;
        for(int i = 1; i < 18; ++ i){
            anc[i][x] = anc[i-1][anc[i-1][x]];
        }
        for(int i : g[x]){
            if(i != fa){
                dfs(i, x);
                siz[x] += siz[i];
            }
        }
    }
    int lca(int x, int y){
        if(dep[x] > dep[y]){
            swap(x, y);
        }
        for(int i = 17; i >= 0; -- i){
            if(dep[anc[i][y]] >= dep[x]){
                y = anc[i][y];
            }
        }
        if(x == y){
            return x;
        }
        for(int i = 17; i >= 0; -- i){
            if(anc[i][x] != anc[i][y]){
                x = anc[i][x];
                y = anc[i][y];
            }
        }
        return anc[0][x];
    }
    void rd(){
        for(int i = 1; i < n; ++ i){
            int u, v;
            scanf("%d%d", &u, &v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        dfs(1, 0);
    }
} T1, T2;

ll T1v[N], T1Bv[N];
void T1add(int x, ll val){
    for(int i = 0; i < x / B; ++ i){
        T1Bv[i] += val;
    }
    for(int i = x / B * B; i <= x; ++ i){
        T1v[i] += val;
    }
}
ll T1qry(int x){
    return T1v[x] + T1Bv[x/B];
}

int iskey[N], lian[N];
int gx[N][B+3];
ll hav[B+3];

void add(int a, int b, int c, int d, ll val){
    T1add(T1.dfn[a], val);
    T1add(T1.dfn[b], val);
    T1add(T1.dfn[c], -val);
    T1add(T1.dfn[d], -val);
    for(int i = 1; i <= iskey[0]; ++ i){
        hav[i] += val * (gx[a][i] + gx[b][i] - gx[c][i] - gx[d][i]);
    }
}
ll asknode(int x){
    return T1qry(T1.dfn[x]) - T1qry(T1.dfn[x] + T1.siz[x]);
}

ll ask(int x, int y, int lca){
    ll ans = 0;
    while(!iskey[x]){
        ans += T1qry(T1.dfn[x]) - T1qry(T1.dfn[x] + T1.siz[x]);
        x = T2.anc[0][x];
    }
    while(!iskey[y]){
        ans += T1qry(T1.dfn[y]) - T1qry(T1.dfn[y] + T1.siz[y]);
        y = T2.anc[0][y];
    }
    while(!iskey[lca]){
        ans -= (T1qry(T1.dfn[lca]) - T1qry(T1.dfn[lca] + T1.siz[lca])) * 2;
        lca = T2.anc[0][lca];
    }
    return ans + hav[iskey[x]] + hav[iskey[y]] - hav[iskey[lca]] * 2;
}
void dfs(int x, int fa){
    for(int i : T1.g[x]){
        if(i == fa){
            continue;
        }
        a[x] -= a[i];
        dfs(i, x);
    }
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++ i){
        scanf("%llu", &a[i]);
    }
    T1.rd();
    T2.rd();
    for(int i = 1; i <= B; ++ i){
        iskey[i] = 1;
    }
    random_shuffle(iskey + 1, iskey + n + 1);
    iskey[1] = 1;
    for(int i = 1; i <= n; ++ i){
        if(iskey[i]){
            iskey[i] = ++ iskey[0];
            for(int j = 1; j <= n; ++ j){
                lian[j] = 0;
            }
            int x = i;
            while(x){
                ++ lian[T1.dfn[x]];
                -- lian[T1.dfn[x]+T1.siz[x]];
                x = T2.anc[0][x];
            }
            for(int j = 1; j <= n; ++ j){
                lian[j] += lian[j-1];
            }
            for(int j = 1; j <= n; ++ j){
                gx[j][iskey[i]] = lian[T1.dfn[j]];
            }
        }
    }
    dfs(1, 0);
    for(int i = 1; i <= n; ++ i){
        add(i, 0, 0, 0, a[i]);
    }
    while(m--){
        int x, y;
        ll k;
        scanf("%d%d%llu", &x, &y, &k);
        int lca = T1.lca(x, y);
        add(x, y, lca, T1.anc[0][lca], k);
        lca = T2.lca(x, y);
        printf("%llu\n", ask(x, y, lca) + asknode(lca));
    }
    return 0;
}