#P18543. Whose Land?

Whose Land?

Whose Land?

小青鱼(Little Cyan Fish,亦称 Xiao Qingyu)是 Memoria Land 的总统。这个国家有 nn 座城市,编号为 1,2,…,n1,2,\ldots,n。有 n−1n-1 条道路,第 ii 条连接城市 ui,viu_i,v_i;任意两座城市之间都有路径,因此这些城市和道路构成一棵树。

城市 x,yx,y 的距离 dis⁡(x,y)\operatorname{dis}(x,y) 是连接它们的最短路径的边数。特别地,dis⁡(x,x)=0\operatorname{dis}(x,x)=0,因为允许空路径。

国庆纪念日将至,小青鱼打算在一些城市放映电影。城市 xx 的居民能够前往城市 yy 观看电影,当且仅当城市 yy 放映电影,且 dis⁡(x,y)≤k\operatorname{dis}(x,y)\le k。

小青鱼有 qq 个相互独立的问题:对于第 ii 个问题,如果恰好在所有编号属于闭区间 [li,ri][l_i,r_i] 的城市放映电影,那么共有多少座城市的居民能够观看电影?

管理国家的工作使小青鱼十分疲惫,请帮助他回答这些问题。

输入格式

第一行包含整数 TT(1≤T≤1051\le T\le10^5),表示测试用例数。

对于每个测试用例:

  • 第一行包含三个整数 n,k,qn,k,q(1≤n≤1051\le n\le10^5,1≤k≤201\le k\le20,1≤q≤5×1051\le q\le5\times10^5)。
  • 接下来 n−1n-1 行,第 ii 行包含两个整数 ui,viu_i,v_i(1≤ui,vi≤n1\le u_i,v_i\le n),表示树的一条边。保证这些边构成一棵树。
  • 接下来 qq 行,第 ii 行包含两个整数 li,ril_i,r_i(1≤li≤ri≤n1\le l_i\le r_i\le n),表示一次询问。

保证同一个输入文件内的所有测试用例满足:

  • nn 的总和不超过 5×1055\times10^5;
  • qq 的总和不超过 5×1055\times10^5;
  • n⋅kn\cdot k 的总和不超过 2×1062\times10^6。

输出格式

对每个询问输出一行,一个整数,表示能够观看电影的城市数。同一城市即使能前往多个放映城市,也只计算一次。按输入顺序输出所有询问的答案。

原样例

2
5 1 2
1 2
1 3
2 4
2 5
2 2
2 3
8 2 3
1 2
1 3
2 4
2 5
4 6
5 7
7 8
2 2
2 5
3 4
4
5
7
8
6

原题没有额外样例解释。放映城市自身因距离为零,也能观看电影。