记录编号	618851	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	举办乘凉州喵，举办乘凉州谢谢喵	最终得分	100
用户昵称	RpUtl	是否通过	通过
代码语言	C++	运行时间	31.836 s
提交时间	2026-09-14 19:10:21	内存使用	87.85 MiB

#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 10;
int sz[N], son[N], top[N], dfn[N], rk[N], cnt;
int Fa[N], de[N], n, q, ans[N];
vector<int> G[N];
void add(int x, int y) {
	G[x].push_back(y);
}
void dfs1(int x, int fa) {
	sz[x] = 1, Fa[x] = fa;
	for (auto y : G[x]) {
		if (y == fa) continue;
		dfs1(y, x); sz[x] += sz[y];
		if (sz[y] > sz[son[x]]) son[x] = y;
	}
	return;
}
void dfs2(int x, int tp) {
	top[x] = tp;
	de[x] = de[Fa[x]] + 1;
	rk[dfn[x] = ++cnt] = x;
	if (!son[x]) return;
	dfs2(son[x], tp);
	for (auto y : G[x]) {
		if (y == son[x] || y == Fa[x]) continue;
		dfs2(y, y);
	}
	return;
}
int LCA(int a, int b) {
	while (top[a] != top[b]) {
		if (de[top[a]] < de[top[b]]) swap(a, b);
		a = Fa[top[a]];
	}
	return de[a] < de[b] ? a : b;
}
struct querys { int d, i, v; }; 
struct BIT {
	int c[2 * N];
	void add(int x, int y) {
		for (x++; x <= 2 * n; x += (x & -x)) c[x] += y;
		return;
	}
	int ask(int x, int y = 0) {
		for (x++; x > 0; x -= (x & -x)) y += c[x];
		return y;
	}
};
namespace PartA {  // tree-devide work
	vector<querys> vec[N];
	int siz[N], vis[N], mx[N], rt, tot;
	struct node { int c, d, x; } p[N];
	BIT T;
	void push(int x, int d, int id) {
		vec[x].push_back({d, id, 1});
	}
	void dfssz(int x, int fa, int s) {
		siz[x] = 1, mx[x] = 0;
		for (auto y : G[x]) {
			if (y == fa || vis[y]) continue;
			dfssz(y, x, s);
			siz[x] += siz[y];
			mx[x] = max(mx[x], siz[y]);
		}
		mx[x] = max(mx[x], s - siz[x]);
		if (mx[x] < mx[rt]) rt = x;
	}
	void dfsdis(int x, int fa, int col, int d) {
		p[++tot] = node{col, d, x};
		for (auto y : G[x]) {
			if (y == fa || vis[y]) continue;
			dfsdis(y, x, col, d + 1);
		}
	}
	void calc(int u) {
		p[tot = 1] = node{u, 0, u};
		for (auto v : G[u]) {
			if (vis[v]) continue;
			dfsdis(v, u, v, 1);
		} 
		int i = 1, j = 1;
		for (; i <= tot; i++) {
			for (; p[j].c != p[i].c; j++) T.add(p[j].d, 1);
			for (auto t : vec[p[i].x]) ans[t.i] += t.v * T.ask(t.d - p[i].d);
		}
		for (j--; j >= 1; j--) T.add(p[j].d, -1);
		i = tot, j = tot;
		for (; i >= 1; i--) {
			for (; p[j].c != p[i].c; j--) T.add(p[j].d, 1);
			for (auto t : vec[p[i].x]) {
				ans[t.i] += t.v * T.ask(t.d - p[i].d);
			}
		}
		for (j++; j <= tot; j++) T.add(p[j].d, -1);
	}
	void solve(int u, int s) {
		vis[u] = 1; calc(u); 
		int S = 0;
		for (auto v : G[u]) {
			if (vis[v]) continue;
			dfssz(v, u, s), S = siz[v];
			rt = 0, dfssz(v, u, S), solve(rt, S); 
		}
	}
	void work() {
		mx[0] = 1e9;
		rt = 0; dfssz(1, 0, n);
		solve(rt, n); return;
	}
}
namespace PartB { // f[u][k] work
	vector<querys> vec[N];
	BIT T;
	void push(int x, int d, int id, int v) {
		vec[dfn[x] + sz[x] - 1].push_back({de[x] + d, id, v});
		if (dfn[x] > 1) vec[dfn[x] - 1].push_back({de[x] + d, id, -v});
	}
	void work() {
		for (int i = 1, x; i <= n; i++) {
			x = rk[i], T.add(de[x], 1);
			for (auto &t : vec[i]) {
				ans[t.i] += t.v * T.ask(t.d);
			}
		}
		return;
	}
}
namespace PartC { // g[u][k] work
	vector<querys> vec[N];
	BIT T;
	void push(int x, int d, int id, int v) {
		vec[x].push_back(querys{d, id, v});
	}
	void dfs(int x, int fa, int d, int v) {
		T.add(d, v);
		for (auto y : G[x]) {
			if (y == fa) continue;
			dfs(y, x, d + 1, v);
		}
		return;
	}
	void DFS(int x, int fa) {
		for (auto y : G[x]) {
			if (y == fa || y == son[x]) continue;
			dfs(y, x, 1, 1);
		}
		for (auto &t : vec[x]) ans[t.i] += t.v * T.ask(t.d);
		for (auto y : G[x]) {
			if (y == fa) continue;
			DFS(y, x);
		}
		for (auto y : G[x]) {
			if (y == fa || y == son[x]) continue;
			dfs(y, x, 1, -1);
		}
	}
	void work() {
		DFS(1, 0);
		return;
	}
}
void query(int x, int t, int id, int d) {
	while (top[x] != top[t]) {
		int u = top[x], v = Fa[u];
		if (d > 0) PartB::push(u, d - 1, id, -1);
		if (d > 0) PartB::push(son[v], d - 1, id, 1);
		x = v;
	}
	return;
}
int main() {
	freopen("clz.in", "r", stdin);
	freopen("clz.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1, u, v; i < n; i++) {
		cin >> u >> v;
		add(u, v), add(v, u);
	}
	dfs1(1, 0);
	dfs2(1, 1);
	cin >> q;
	int x, y, d, z;
	for (int i = 1; i <= q; i++) {
		cin >> x >> y >> d;
		if (de[x] > de[y]) swap(x, y);
		z = LCA(x, y); 
		if (z == x) {
			PartA::push(x, d, i); ans[i]++;
			PartB::push(x, d, i, -1);
			PartC::push(y, d, i, 1);
			if (Fa[x]) PartC::push(Fa[x], d, i, -1);
			ans[i] += de[y] - de[x] + 1; 
			if (son[y] && d > 0) PartB::push(son[y], d - 1, i, 1);
			query(y, x, i, d);
		} else {
			PartA::push(z, d, i); ans[i]++;
			PartB::push(z, d, i, -2);
			PartC::push(x, d, i, 1);
			PartC::push(y, d, i, 1);
			if (Fa[z]) PartC::push(Fa[z], d, i, -2);
			ans[i] += de[x] + de[y] - 2 * de[z] + 2;
			if (son[x] && d > 0) PartB::push(son[x], d - 1, i, 1);
			if (son[y] && d > 0) PartB::push(son[y], d - 1, i, 1);
			query(y, z, i, d);
			query(x, z, i, d);
		}
	}
	PartA::work();
	PartB::work();
	PartC::work();
	for (int i = 1; i <= q; i++) {
		cout << ans[i] << '\n';
	}
	return 0;
}