MnZn 一个点都没过 QAQ

#include <cstdio>
#include <vector>
#include <algorithm>

typedef long long ll;

const ll mod = 998244353;
const int N = 3e5 + 5;
const int LogN = 25;
const int K = 51;

int n, x, y, m, k;
int fa[N][LogN], depth[N];
ll sum[N][K];
std::vector < int > edge[N];

ll quick_pow(ll a, int b)
{
    ll res(1);
    while (b)
    {
        if (b & 1)
            res *= a, res %= mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

void dfs(int now, int father)
{
    depth[now] = depth[father] + 1;
    fa[now][0] = father;
    int i;
    for (i = 1; i < LogN; i++)
        fa[now][i] = fa[fa[now][i - 1]][i - 1];
    for (i = 1; i < K; i++)
    {
        sum[now][i] = sum[father][i] + quick_pow(depth[now], i);
        sum[now][i] %= mod;
    }
    for (i = 0; i < edge[now].size(); i++)
        if (edge[now][i] != father)
            dfs(edge[now][i], now);
}

int LCA(int x, int y)
{
    if (depth[x] > depth[y])
        std::swap(x, y);
    int i, delta = depth[y] - depth[x];
    for (i = LogN - 1; delta; i--, delta >>= 1)
        if (delta & 1)
            y = fa[y][i];
    if (x == y)
        return x;
    for (i = LogN - 1; i >= 0; i--)
        if (fa[x][i] != fa[y][i])
        {
            x = fa[x][i];
            y = fa[y][i];
        }
    if (x == y)
        return x;
    return fa[x][0];
}

int main()
{
    scanf("%d", &n);
    int i, lca;
    for (i = 1; i < n; i++)
    {
        scanf("%d %d", &x, &y);
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    depth[0] = -1;
    dfs(1, 0);
    scanf("%d", &m);
    while (m--)
    {
        scanf("%d %d %d", &x, &y, &k);
        lca = LCA(x, y);
        printf("%lld\n", ((sum[x][k] + sum[y][k]) % mod - (sum[fa[lca][0]][k] + sum[lca][k]) % mod + mod) % mod);
    }
    return 0;
}