#P18887. [2026多校联测]态度是心的面具

[2026多校联测]态度是心的面具

题目描述

方源发现了 nn 座蛊仙福地,编号为 1∼n1 \sim n。他想要从中找到仙蛊提升实力。因为方源手中有定仙游,因此他可以从一个蛊仙福地传送的一些其它蛊仙福地。具体的,有 n−1n - 1 个 双向 传送信息,第 ii 条信息 (ui,vi)(u_i, v_i) 表示当位于 uiu_i 时,方源可传送到 viv_i,或当位于 viv_i,可传送到 uiu_i,并且保证任意两个福地之间都可通过若干次传送到达。 不难理解所有的蛊仙福地构成了一个 树形结构。

但是方源的仙元是有限的,不能够无限次传送。作为一个老谋深算,想要掌握一切局面的人,方源有 qq 次规划,每次规划都给出树上一条路径的两个端点 xi,yix_i, y_i,方源想知道如果他可以任意选择路径 xi→yix_i \to y_i 上的一个点作为起点,在传送次数不超过 did_i 次 的条件下,有多少个蛊仙福地能够被他到达。

形式化题意:

给定一棵 nn 个节点的树,树的一条边为 (ui,vi)(u_i, v_i)。 qq 次询问,每次询问给定 xi,yi,dix_i, y_i, d_i,你需要求出树上有多少个点到路径 xi→yix_i \to y_i 的最小距离不超过 did_i。

输入格式

第一行一个整数 nn,表示树的节点数。

第二行到第 nn 行,每行两个整数 ui,viu_i,v_i,表示树的一条边。

第 n+1n + 1 行一个整数 qq。

接下来 qq 行每行三个整数 xi,yi,dix_i, y_i, d_i,描述一次询问的路径和邻域半径。

输出格式

共 qq 行,每行一个整数,第 ii 行表示第 ii 次询问的答案。

样例输入

6
1 2
2 3
2 4
1 5
4 6
3
2 4 1
1 1 0
3 2 1

样例输出

5
1
4

数据规模

对于全部的数据:1≤n,q≤2×1051 \leq n,q \leq 2 \times 10^5。

  • 子任务 11(20分):n,q≤5000n, q \leq 5000。
  • 子任务 22(20分):xi=yix_i = y_i
  • 子任务 33(10分):di=0d_i = 0
  • 子任务 44(10分):di=1d_i = 1
  • 子任务 55(10分):保证 xi=1x_i = 1
  • 子任务 66(10分):保证点 ii 的父亲在 [1,i−1][1, i - 1] 随机生成
  • 子任务 77:无特殊限制