luogu#P3899. [湖南集训] 更为厉害

[湖南集训] 更为厉害

题目描述

T\text T 为一棵有根树,我们做如下的定义:

  • aabbT\text T 中的两个不同节点。如果 aabb 的祖先,那么称“aabb 更为厉害”。
  • aabbT\text T 中的两个不同节点。如果 aabb 在树上的距离不超过某个给定常数 xx,那么称“ aabb 彼此彼此”。

给定一棵 nn 个节点的有根树 T\text T,节点的编号为 11nn,根节点为 11 号节点。 你需要回答 qq 个询问,询问给定两个整数 ppkk,问有多少个有序三元组 (a,b,c)(a,b,c) 满足:

  1. a,b,ca,b,cT\text T 中三个不同的点,且 aapp 号节点;
  2. aabb 都比 cc 更为厉害;
  3. aabb 彼此彼此。这里彼此彼此中的常数为给定的 kk

输入格式

输入文件的第一行含有两个正整数 nnqq,分别代表有根树的点数与询问的个数。

接下来 n1n - 1 行,每行描述一条树上的边。每行含有两个整数 uuvv,代表在节点 uuvv 之间有一条边。

接下来 qq 行,每行描述一个操作。第 ii 行含有两个整数,分别表示第 ii 个询问的 ppkk

输出格式

输出 qq 行,每行对应一个询问,代表询问的答案。

5 3
1 2
1 3
2 4
4 5
2 2
4 1
2 3
3
1
3

提示

样例中的树如下图所示:

对于第一个和第三个询问,合法的三元组有 (2,1,4)(2,1,4)(2,1,5)(2,1,5)(2,4,5)(2,4,5)

对于第二个询问,合法的三元组只有 (4,2,5)(4,2,5)

所有测试点的数据规模如下(注意,洛谷并不按照以下方式评测):

对于全部测试数据的所有询问,1p,kn1\le p,k \le n

  • 2023.9.15 添加一组 hack 数据。