3827. 举办乘凉州喵，举办乘凉州谢谢喵

【题目背景】

在塔历 $545$ 年，塔国进行了第 $510$ 届国王的选举。

塔国共有 $n$ 个城市，各大城市间共建设了 $n−1$ 条道路， 这 $n−1$ 条道路将这些城市两两连通，也就是说，塔国的地图可以看作是一棵大小为 $n$ 的树。 程良洲成功当选，这引起了一些地方政权的不满。

于是，在塔历 $546$ 年，塔国爆发了 $q$ 次革命，第 $i$ 次革命是由从 $x_i$ 出发到 $y_i$ 这一条简单路径上所有的城市联合发起的。

但是，塔国的军队训练有素，对于第 $i$ 次革命，革命军仅仅只是前进了 $d_i$ 的距离就被镇压了。

作为塔国记录历史的史官，你奉命记录下了这 $q$ 次革命，并被要求统计出，每次革命共影响了多少个城市。

【题目描述】

给出一棵大小为 $n$ 的树。

定义 $x \rightarrow y$ 表示树上从 $x$ 到 $y$ 的简单路径，树上 $x, y$ 两点的距离 $\mathrm{dis}(x, y)$ 为 $x \rightarrow y$ 包含的边数。

定义树上一个点 $u$ 到树上一条简单路径 $x \rightarrow y$ 的距离为 $\min\limits_{v∈x \rightarrow y}{\mathrm{dis}(u, v)}$。

有 $q$ 次询问，第 $i$ 次询问给出三个整数 $x_i, y_i, d_i$，满足 $1 \le x_i, y_i \le n, 0 \le d_i \lt n$，你需要求出距离 $x_i \rightarrow y_i$ 小于等于 $d_i$ 的点数。

【输入格式】

第一行一个整数 $n$ 。

第二行到第 $n$ 行，每行两个整数 $u_i,v_i$，表示树的一条边。

第 $n+1$ 行一个整数 $q$。

接下来 $q$ 行每行三个整数 $x_i,y_i,d_i$，描述了一次询问。

【输出格式】

共 $q$ 行，每行一个整数，第 $i$ 行表示第 $i$ 个询问的答案。

【样例输入】

6
1 2
2 3
2 4
1 5
4 6
3
2 4 1
1 1 0
3 2 1

【样例输出】

5
1
4

【数据规模与约定】

对于全部的数据，$1≤n,q≤2×10^5$。

$\bullet$ 子任务 $1$（$7$ 分）：$n,q≤5000$。

$\bullet$ 子任务 $2$（$8$ 分）：$x_i=y_i$。

$\bullet$ 子任务 $3$（$23$ 分）：$x_i \rightarrow y_i$ 最多只会包含 $20$ 个点。

$\bullet$ 子任务 $4$（$22$ 分）：$d_i≤20$。

$\bullet$ 子任务 $5$（$20$ 分）：$n,q≤5×10^4$。

$\bullet$ 子任务 $6$（$20$ 分）：无特殊限制。

【来源】

2022 集训队互测 Round3 T2