luogu#P3899. [湖南集训] 更为厉害
[湖南集训] 更为厉害
题目描述
设 为一棵有根树,我们做如下的定义:
- 设 和 为 中的两个不同节点。如果 是 的祖先,那么称“ 比 更为厉害”。
- 设 和 为 中的两个不同节点。如果 与 在树上的距离不超过某个给定常数 ,那么称“ 与 彼此彼此”。
给定一棵 个节点的有根树 ,节点的编号为 到 ,根节点为 号节点。 你需要回答 个询问,询问给定两个整数 和 ,问有多少个有序三元组 满足:
- 为 中三个不同的点,且 为 号节点;
- 和 都比 更为厉害;
- 和 彼此彼此。这里彼此彼此中的常数为给定的 。
输入格式
输入文件的第一行含有两个正整数 和 ,分别代表有根树的点数与询问的个数。
接下来 行,每行描述一条树上的边。每行含有两个整数 和 ,代表在节点 和 之间有一条边。
接下来 行,每行描述一个操作。第 行含有两个整数,分别表示第 个询问的 和 。
输出格式
输出 行,每行对应一个询问,代表询问的答案。
5 3
1 2
1 3
2 4
4 5
2 2
4 1
2 3
3
1
3
提示
样例中的树如下图所示:
对于第一个和第三个询问,合法的三元组有 、 和 。
对于第二个询问,合法的三元组只有 。
所有测试点的数据规模如下(注意,洛谷并不按照以下方式评测):
对于全部测试数据的所有询问,。
- 2023.9.15 添加一组 hack 数据。