题目背景

在塔历 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$ 两点的距离 $\operatorname{dis}(x, y)$ 为 $x \rightarrow y$ 包含的边数。

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

有 $q$ 次询问，第 $i$ 次询问给出三个整数 $x_i, y_i, d_i$ ，满足 $1 \leq x_i, y_i \leq n, 0 \leq d_i < 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$。

• 子任务 1（7 分）：$n,q≤5000$。
• 子任务 2（8 分）：$x_i = y_i$。
• 子任务 3（23 分）：$x_i \to y_i$ 最多只会包含 $20$ 个点。
• 子任务 4（22 分）：$d_i \le 20$。
• 子任务 5（20 分）：$n,q \le 5 \times 10^4$。
• 子任务 6（20 分）：无特殊限制。