#P18543. Whose Land?
Whose Land?
Whose Land?
小青鱼(Little Cyan Fish,亦称 Xiao Qingyu)是 Memoria Land 的总统。这个国家有 座城市,编号为 。有 条道路,第 条连接城市 ;任意两座城市之间都有路径,因此这些城市和道路构成一棵树。
城市 的距离 是连接它们的最短路径的边数。特别地,,因为允许空路径。
国庆纪念日将至,小青鱼打算在一些城市放映电影。城市 的居民能够前往城市 观看电影,当且仅当城市 放映电影,且 。
小青鱼有 个相互独立的问题:对于第 个问题,如果恰好在所有编号属于闭区间 的城市放映电影,那么共有多少座城市的居民能够观看电影?
管理国家的工作使小青鱼十分疲惫,请帮助他回答这些问题。
输入格式
第一行包含整数 (),表示测试用例数。
对于每个测试用例:
- 第一行包含三个整数 (,,)。
- 接下来 行,第 行包含两个整数 (),表示树的一条边。保证这些边构成一棵树。
- 接下来 行,第 行包含两个整数 (),表示一次询问。
保证同一个输入文件内的所有测试用例满足:
- 的总和不超过 ;
- 的总和不超过 ;
- 的总和不超过 。
输出格式
对每个询问输出一行,一个整数,表示能够观看电影的城市数。同一城市即使能前往多个放映城市,也只计算一次。按输入顺序输出所有询问的答案。
原样例
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
原题没有额外样例解释。放映城市自身因距离为零,也能观看电影。