0 pts 求条

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

template <typename T>
inline void read(T &x)
{
	x = 0;
	bool f = false;
	char v = getchar();
	while(v != '-' && (v < '0' || v > '9')) v = getchar();
	if(v == '-') f = true, v = getchar();
	while(v >= '0' && v <= '9') x = (x << 3) + (x << 1) + (v & 15), v = getchar();
	if(f) x = -x;
}
template <typename T>
inline void write(T x)
{
	if(x < 0) putchar('-'), x = -x;
	if(x < 10) putchar(x | 48);
	else write(x / 10), putchar(x % 10 | 48); 
}
const int maxn = 1e6, maxl = 30, maxk = 50;
const long long mod = 998244353;
int n, q, u, v, k;
int fa[maxn + 5][maxl + 5];
int lg[maxn + 5];
int dep[maxn + 5];
long long sum[maxn + 5][maxk + 5];
vector<int> g[maxn + 5];
void add(int u, int v)
{
	g[u].push_back(v);
}
void dfs(int now, int f)
{
	fa[now][0] = f;
	dep[now] = dep[f] + 1;
	for(int i = 1; i <= lg[dep[now]]; ++ i)
	{
		fa[now][i] = fa[fa[now][i - 1]][i - 1]; 
	}
	for(int i : g[now]) 
	{
		if(i != f) dfs(i, now);
	}
}
int lca(int a, int b)
{
	if(dep[a] < dep[b]) swap(a, b);
	while(dep[a] > dep[b]) a = fa[a][lg[dep[a] - dep[b]]];
	if(a == b) return a;
	for(int i = lg[dep[a]]; i >= 0; -- i)
	{
		if(fa[a][i] != fa[b][i]) a = fa[a][i], b = fa[b][i];
	}
	return fa[a][0];
}
void init(int maxv)
{
	for(int i = 2; i <= maxv; ++ i) lg[i] = lg[i >> 1] + 1;
	for(int i = 1; i <= maxv; ++ i)
	{
		sum[i][0] = 1;
		for(int j = 1; j <= maxk; ++ j)
		{
			sum[i][j] = 1ll * sum[i][j - 1] * i % mod;
			sum[i][j] %= mod;
		}
		for(int j = 1; j <= maxk; ++ j)
		{
			sum[i][j] += sum[i - 1][j];
			sum[i][j] %= mod;
		}
	}
}
int main(void)
{
	read(n);
	init(n + 1);
	for(int i = 1; i < n; ++ i)
	{
		read(u), read(v);
		add(u, v);
		add(v, u);
	}
	dfs(1, 0);
	read(q);
	while(q--)
	{
		read(u), read(v), read(k);
		int t = lca(u, v);
		t = dep[t], u = dep[u], v = dep[v];
		-- t, -- u, -- v;
		long long ans = sum[u][k] - sum[t][k];
		ans %= mod;
		ans += mod;
		ans += sum[v][k];
		ans %= mod;
		ans -= sum[fa[t][0]][k];
		ans %= mod;
		ans += mod << 1;
		ans %= mod;
		write(ans), putchar('\n');
	}
	return 0; 
}