TLE 100pts求条 玄关

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int MAXN = 3e5 + 5;
const int LOG = 20;
const int MOD = 998244353;
int n;
vector<int> g[MAXN];
int sum[MAXN][55], dep[MAXN];
ll quick_pow(int a, int b) {
	if (b == 0) return 1;
	if (b == 1) return a;
	ll k = quick_pow(a, b / 2);
	if (b % 2 == 0) {
		return k * k % MOD; 
	} else {
		return k * k % MOD * a % MOD;
	}
}
void addEdge(int u, int v) {
	g[u].push_back(v);
	g[v].push_back(u);
}
void prepare(int u, int pa, int k, bool flag) {
	if (flag) dep[u] = dep[pa] + 1;
	sum[u][k] = (sum[pa][k] + quick_pow(dep[u], k)) % MOD;
	for (int v : g[u]) {
		if (v != pa) {
			prepare(v, u, k, flag);
		}
	}
}
struct LCA {
	int fa[MAXN][LOG];
	void dfs(int u, int pa) {
		fa[u][0] = pa;
		for (int i = 1; i < LOG; i++) {
			fa[u][i] = fa[fa[u][i - 1]][i - 1];
		}
		for (int v : g[u]) {
			if (v != pa) {
				dfs(v, u);
			}
 		}
	}
	int lca(int u, int v) {
		if (dep[u] < dep[v]) swap(u, v);
		for (int i = LOG - 1; i >= 0; i--) {
			if (dep[fa[u][i]] >= dep[v]) {
				u = fa[u][i];
			}
		}
		if (u == v) return u;
		for (int i = LOG - 1; i >= 0; i--) {
			if (fa[u][i] != fa[v][i]) {
				u = fa[u][i], v = fa[v][i];
			}
		}
		return fa[u][0];
	}
}l;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		addEdge(u, v);
	}
	for (int i = 1; i <= 50; i++) {
		dep[0] = -1;
		prepare(1, 0, i, i == 1);
	}
	l.dfs(1, 0);
	int q;
	cin >> q;
	while (q--) {
		int u, v, k;
		cin >> u >> v >> k;
		int L = l.lca(u, v);
		ll ans = (sum[u][k] + sum[v][k]) % MOD;
		ans = (ans - sum[L][k] + MOD) % MOD;
		if (l.fa[L][0]) ans = (ans - sum[l.fa[L][0]][k] + MOD) % MOD;
		cout << ans << endl;
	}
	return 0;
}