1802: 最短距离
内存限制：256 MB
时间限制：5.000 S
评测方式：文本比较
命题人：
提交：6
解决：3
题目描述
给定一棵包含 
个顶点的树 
，以及 
个查询请求。每个查询包含三个参数：
、
和 
。其中 和 是树中的两个顶点， 是一个整数。对于每个查询，你需要计算树中所有顶点到从 到 的简单路径上的最近距离恰好为 的顶点数量。
输入
第一行，两个正整数n和m。（1
n,m1e5）
接下来n-1行，每行两个正整数x,y。点x和点y之间有一条边。（1x,yn)
最后m行，每行三个正整数x，y，k。（1x,yn，1k100）
输出
对于每次询问，输出一个整数作为答案
每个答案占一行
样例输入 复制
7 2
1 2
1 3
2 4
2 5
4 6
4 7
5 7 1
5 7 2样例输出 复制
2
1提示
如图所示， 到
的简单路径的点集为
，树上到点集中的点的最近距离为
的点有
，故答案为
。