P6589 『JROI-1』 关系树

小 L 有许多喜欢的游戏角色，他把这些游戏角色按照一定的关系联系起来。这些游戏角色和他们之间的关系构成了一棵树，小 L 把这棵树称之为「关系树」。

关系树是由 $n$ 个点和 $n-1$ 条无向边组成的一棵树。 对于一张给定的图 $G$，定义图 $G$ 对于点集 $E$ 的 **顶点导出子图** 为点集 $E$ 和所有的 **两个端点都属于 $E$** 且属于原图 $G$ 的边组成的图。 定义一张图是 **整洁的**，当且仅当图中任意两点 $u,v$，$u$ 和 $v$ **不连通** 或 **距离不超过** $k$。 小 L 想要知道对于一组 $l,r(l \leq r)$，有多少对 $(a,b)$，满足 $l\leq a\leq b\leq r$，且所有序号在 $a$ 和 $b$ 之间（包括 $a,b$）的点组成的顶点导出子图是 **整洁的**。不仅如此，他还想问你所有的区间长度（即 $b-a+1$）之和。 因为小 L 喜欢问问题，所以你一共需要回答 $q$ 组询问。

第一行有三个整数 $n$，$q$，$k$，意义如上。 接下来 $n-1$ 行，每行两个整数 $u$，$v$，描述一条边。 接下来 $q$ 行，每行两个整数 $l$，$r$，表示一组询问。

$q$ 行，每行两个整数，依次为满足的 $(a,b)$ 组数和所有的区间长度之和。

#### 样例 1 解释 形成的关系树如图  满足的 $(a,b)$ 有 $(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(2,5),(3,3),(3,4),(3,5),(4,4),(4,5),(5,5)$。 三组询问的答案依次为 $6,10$，$10,20$，$14,30$。 -------------------------------- #### 数据规模与约定 **本题采用捆绑测试**。 + Subtask 1 ( $10\%$ )：$n\leq 2000$。 + Subtask 2 ( $30\%$ )：$n\leq 2\times 10^4$，形成的关系树为一条链。 + Subtask 3 ( $60\%$ )：$n\leq 2\times 10^4$。 + Subtask 4 ( 加强版数据，时限 $4.5s$ )：无特殊限制。 对于 $100\%$ 的测试点，保证 $1\leq n \leq 8\times 10^4$，$1\leq q \leq 10^5$，$0\leq k