P14380 【MX-S9-T3】「LAOI-16」天外来物

> 你像天外来物一样求之不得，你在世俗里的名字不重要了。 > > 正好我隐藏的人格是契而不舍，直到蜂拥而至的人都透明了。

ChA 在天上点缀了 $n$ 颗星星，编号为 $1 \sim n$。他们之间有 $n - 1$ 对星链。 Wa1 仰望星空，手指沿着星链移动，她发现星星构成了一棵树结构。 于是 Wa1 为每一颗星星附上了 $1\sim n$ 的编号。 “我要随便选两个数字 $l, r$，然后用手指把编号在 $[l,r]$ 的星星，两两沿着星链按**最短路径**连接。我手指划过的所有星星和星链就属于同一个星系。” “简单地说，我要让这个星系**包含编号在 $[l,r]$ 中的所有点**并且**连通**。虽然有很多，但我只要满足条件的**最小**的星系。” “这样生成的星系叫作 $[l,r]$ 的天外来物，即 $f(l,r)$。” ChA 共 $q$ 次望向那片曾经的星空。他每次会随意想两个整数 $L_i,R_i$。他想知道有多少种不同的 $f(l,r)$，其中 $L_i\le l\le r\le R_i$。 称 $f$ 相同，当且仅当其包含的点集相同。

第一行，两个整数 $n,q$，具体意义见题目描述。 接下来 $n-1$ 行，每行两个整数 $x,y$，表示一条星链连接的两颗星星。 接下来 $q$ 行，每行两个整数 $L_i,R_i$。

共 $q$ 行，每行一个整数，表示满足 $L\le l\le r\le R$ 互不相同 $f(l,r)$ 的个数。

**【样例解释 #1】** 以下是所有合法 $f(i,j)$ 的对应集合。 $f(1,1)=\{1\}$，$f(2,2)=\{2\}$，$f(3,3)=\{3\}$，$f(4,4)=\{4\}$，$f(5,5)=\{5\}$。 $f(1,2)=\{1,2\}$，$f(2,3)=\{2,3\}$，$f(3,4)=\{1,2,3,4\}$，$f(4,5)=\{1,2,4,5\}$。 $f(1,3)=\{1,2,3\}$，$f(2,4)=\{1,2,3,4\}$，$f(3,5)=\{1,2,3,4,5\}$。 $f(1,4)=\{1,2,3,4\}$，$f(2,5)=\{1,2,3,4,5\}$。 $f(1,5)=\{1,2,3,4,5\}$。 **【样例解释 #2】** 该样例满足测试点 $1, 2$ 的约束条件。 **【样例 #3】** 见选手目录下的 $\textbf{\textit{unearthed/unearthed3.in}}$ 与 $\textbf{\textit{unearthed/unearthed3.ans}}$。 该样例满足测试点 $1, 2$ 的约束条件。 **【样例 #4】** 见选手目录下的 $\textbf{\textit{unearthed/unearthed4.in}}$ 与 $\textbf{\textit{unearthed/unearthed4.ans}}$。 该样例满足测试点 $3, 4$ 的约束条件。 **【样例 #5】** 见选手目录下的 $\textbf{\textit{unearthed/unearthed5.in}}$ 与 $\textbf{\textit{unearthed/unearthed5.ans}}$。 该样例满足测试点 $5\sim 8$ 的约束条件。 **【样例 #6】** 见选手目录下的 $\textbf{\textit{unearthed/unearthed6.in}}$ 与 $\textbf{\textit{unearthed/unearthed6.ans}}$。 该样例满足测试点 $9\sim 11$ 的约束条件。 **【样例 #7】** 见选手目录下的 $\textbf{\textit{unearthed/unearthed7.in}}$ 与 $\textbf{\textit{unearthed/unearthed7.ans}}$。 该样例满足测试点 $12, 13$ 的约束条件。 **【样例 #8】** 见选手目录下的 $\textbf{\textit{unearthed/unearthed8.in}}$ 与 $\textbf{\textit{unearthed/unearthed8.ans}}$。 该样例满足测试点 $14, 15$ 的约束条件。 **【样例 #9】** 见选手目录下的 $\textbf{\textit{unearthed/unearthed9.in}}$ 与 $\textbf{\textit{unearthed/unearthed9.ans}}$。 该样例满足测试点 $16\sim 19$ 的约束条件。 **【样例 #10】** 见选手目录下的 $\textbf{\textit{unearthed/unearthed10.in}}$ 与 $\textbf{\textit{unearthed/unearthed10.ans}}$。 该样例满足测试点 $20\sim 25$ 的约束条件。 **【数据范围】** 本题共 $25$ 个测试点，每个 $4$ 分。 对于所有测试数据，保证： - $1\le n,q\le 5\times 10^5$； - $1\le L_i\le R_i\le n$； - $1\le x,y\le n$，保证输入的边构成树。 ::cute-table{tuack} |测试点编号|$n,q \le$|特殊性质| |:--:|:--:|:--:| |$1, 2$|$100$|无| |$3, 4$|$600$|^| |$5\sim 8$|$5000$|^| |$9\sim 11$|$5\times 10^5$|A| |$12, 13$|^|B| |$14, 15$|^|C| |$16\sim 19$|$10^5$|无| |$20\sim 25$|$5\times 10^5$|^| 特殊性质 A：$q = 1$。 特殊性质 B：对于所有 $2 \le i \le n$，均有 $i$ 与 $i-1$ 连边。 特殊性质 C：对于所有 $2 \le i \le n$，均有 $i$ 与 $1$ 连边。