C. 杰哥，你带我走吧！杰哥

题解

前缀和思想，预处理出每个点到根节点的点权和，记为 $prepre$，然后每次询问只需查询最近公共祖先 $\mathrm{lca}(u,v)\backslash operatorname\{lca\}(u,v)$，然后输出 $pre[u]+pre[v]-pre[\mathrm{lca}(u,v)]-pre[father[\mathrm{lca}(u,v)]]pre[u]+pre[v]-pre[\backslash operatorname\{lca\}(u,v)]-pre[father[\backslash operatorname\{lca\}(u,v)]]$。$kk$ 最大值为 $5050$，预处理 $5050$ 次前缀和即可。

std:

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

using ll = long long;
using VI = vector<int>;
using PII = pair<int, int>;

const int maxn = 1e5 + 5;
const ll mod = 1e9+7;

VI g[maxn];
int depth[maxn], father[maxn][30];
ll s[maxn][55], val[maxn];

ll qpow(ll a, ll x)
{
    ll ret = 1;
    while (x)
    {
        if (x & 1)
            ret *= a;
        ret %= mod;
        a *= a;
        a %= mod;
        x >>= 1;
    }
    return ret;
}

void dfs(int now, int fa)
{
    depth[now] = depth[fa] + 1;
    father[now][0] = fa;
    for (int i = 0; i <= 50; ++i)
    {
        s[now][i] = s[fa][i] + qpow(val[now], i);
        s[now][i] %= mod;
    }
    for (int i = 1; (1 << i) <= depth[now]; ++i)
        father[now][i] = father[father[now][i - 1]][i - 1];
    for (int next : g[now])
        if (next != fa)
            dfs(next, now);
}

int lca(int x, int y)
{
    if (depth[x] < depth[y])
        swap(x, y);
    for (int i = 22; i >= 0; --i)
    {
        if (depth[father[x][i]] >= depth[y])
            x = father[x][i];
    }
    if (x == y)
        return x;
    for (int i = 22; i >= 0; --i)
    {
        if (father[x][i] != father[y][i])
        {
            x = father[x][i];
            y = father[y][i];
        }
    }
    return father[x][0];
}

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        cin >> val[i];
    for (int i = 1; i < n; ++i)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0);
    while (m--)
    {
        int u, v, k;
        cin >> u >> v >> k;
        int f = lca(u, v);
        ll ans = (s[u][k] + s[v][k]) % mod;
        ans -= (s[f][k] + s[father[f][0]][k]) % mod;
        ans = (ans + mod) % mod;
        cout << (ans + mod) % mod << endl;
    }
    return 0;
}