树链剖分+树上前缀和
说来有趣，中午刚学完树上前缀和，立马就在这用上了
注意这里是点的前缀和，算出每个点的前缀和后，会发现有不少重复的，减去重复的点权和，就可以了。
利用mi[j]，数组记录每个深度的第j次方，s[v][j]记录根节点到v点j次方的前缀和。
代码只需在倍增的模板上稍加改造就好。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int mod = 998244353,N=3e5+10;
vector<int> g[N];
LL mi[55], dep[N],s[N][50],fa[N][22];
void dfs(int u, int father) {
for (int i = 1; i <= 19; i++) {
fa[u][i] = fa[fa[u][i - 1]][i - 1];
}
for (auto v : g[u]) {
if (v == father) continue;
fa[v][0] = u;
dep[v] = dep[u] + 1;
for (int i = 1; i <= 50; i++) mi[i] = mi[i - 1] * dep[v] % mod;
for (int i = 1; i <= 50; i++) s[v][i] = (s[u][i] + mi[i]) % mod;
dfs(v, u);
}
}
int lca(int u, int v) {
if (dep[u] < dep[v]) swap(v, u);
for (int i = 19; i >= 0; i--) {
if (dep[fa[u][i]] >= dep[v]) {//注意深度不要搞错
u = fa[u][i];
}
}
if (u == v) return v;
for (int i = 19; i >= 0; i--) {
if (fa[u][i] != fa[v][i]) {
u = fa[u][i], v = fa[v][i];
}
}
return fa[u][0];
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin >> n;
for (int i = 1; i < n; i++) {
int x, y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
mi[0] = 1;
dfs(1, 0);
int m;
cin >> m;
while (m--) {
int x, y, k;
cin >> x >> y >> k;
int w = lca(x, y);
cout <<(s[x][k] + s[y][k] - s[w][k]-s[fa[w][0]][k] + 2ll * mod) % mod << '\n';
}
return 0;
}