#1657. 举办乘凉州喵,举办乘凉州谢谢喵
举办乘凉州喵,举办乘凉州谢谢喵
举办乘凉州喵,举办乘凉州谢谢喵
题目描述
标题: 举办乘凉州喵,举办乘凉州谢谢喵 - Problem - QOJ.ac
#5020. 举办乘凉州喵,举办乘凉州谢谢喵
The problem was used in the following contests:
题目背景
在塔历 545 年,塔国进行了第 510 届国王的选举。
塔国共有 n 个城市,各大城市间共建设了 n−1 条道路, 这 n−1 条道路将这些城市两两连通,也就是说,塔国的地图可以看作是一棵大小为 n 的树。 程良洲成功当选,这引起了一些地方政权的不满。
于是,在塔历 546 年,塔国爆发了 q 次革命,第 i 次革命是由从 xi 出发到 yi 这一条简单路径上所有的城市联合发起的。
但是,塔国的军队训练有素,对于第 i 次革命,革命军仅仅只是前进了 di 的距离就被镇压了。
作为塔国记录历史的史官,你奉命记录下了这 q 次革命,并被要求统计出,每次革命共影响了多少个城市。
题目描述
给出一棵大小为 n 的树。
定义 x→y 表示树上从 x 到 y 的简单路径,树上 x,y 两点的距离 dis(x,y) 为 x→y 包含的边数。
定义树上一个点 u 到树上一条简单路径 x→y 的距离为 minv∈x→ydis(u,v) 。
有 q 次询问,第 i 次询问给出三个整数 xi,yi,di ,满足 1≤xi,yi≤n,0≤di<n ,你需要求出距离 xi→yi 小于等于 di 的点数。
输入格式
第一行一个整数 n 。
第二行到第 n 行,每行两个整数 ui,vi ,表示树的一条边。
第 n+1 行一个整数 q。
接下来 q 行每行三个整数 xi,yi,di,描述了一次询问。
输出格式
共 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×105。
- 子任务 1(7 分):n,q≤5000。
- 子任务 2(8 分):xi=yi。
- 子任务 3(23 分):xi→yi 最多只会包含 20 个点。
- 子任务 4(22 分):di≤20。
- 子任务 5(20 分):n,q≤5×104。
- 子任务 6(20 分):无特殊限制。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
6
1 2
2 3
2 4
1 5
4 6
3
2 4 1
1 1 0
3 2 1
5
1
4