#P18887. [2026多校联测]态度是心的面具
[2026多校联测]态度是心的面具
题目描述
方源发现了 座蛊仙福地,编号为 。他想要从中找到仙蛊提升实力。因为方源手中有定仙游,因此他可以从一个蛊仙福地传送的一些其它蛊仙福地。具体的,有 个 双向 传送信息,第 条信息 表示当位于 时,方源可传送到 ,或当位于 ,可传送到 ,并且保证任意两个福地之间都可通过若干次传送到达。 不难理解所有的蛊仙福地构成了一个 树形结构。
但是方源的仙元是有限的,不能够无限次传送。作为一个老谋深算,想要掌握一切局面的人,方源有 次规划,每次规划都给出树上一条路径的两个端点 ,方源想知道如果他可以任意选择路径 上的一个点作为起点,在传送次数不超过 次 的条件下,有多少个蛊仙福地能够被他到达。
形式化题意:
给定一棵 个节点的树,树的一条边为 。 次询问,每次询问给定 ,你需要求出树上有多少个点到路径 的最小距离不超过 。
输入格式
第一行一个整数 ,表示树的节点数。
第二行到第 行,每行两个整数 ,表示树的一条边。
第 行一个整数 。
接下来 行每行三个整数 ,描述一次询问的路径和邻域半径。
输出格式
共 行,每行一个整数,第 行表示第 次询问的答案。
样例输入
6
1 2
2 3
2 4
1 5
4 6
3
2 4 1
1 1 0
3 2 1
样例输出
5
1
4
数据规模
对于全部的数据:。
- 子任务 (20分):。
- 子任务 (20分):
- 子任务 (10分):
- 子任务 (10分):
- 子任务 (10分):保证
- 子任务 (10分):保证点 的父亲在 随机生成
- 子任务 :无特殊限制