QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 1024 MB Total points: 100
Statistics

题目背景

在塔历 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 分):无特殊限制。