P6374 「StOI-1」树上询问

给定一棵 $n$ 个点的无根树，有 $q$ 次询问。 每次询问给一个参数三元组 $(a,b,c)$，求有多少个 $i$ 满足这棵树在以 $i$ 为根的情况下 $a$ 和 $b$ 的 [LCA](https://www.luogu.com.cn/problem/P3379) 为 $c$。

第一行 $2$ 个数，为 $n$ 和 $q$。 接下来 $n-1$ 行，每行 $2$ 个数，表示树的一条边。 接下来 $q$ 行，每行 $3$ 个数，为 $(a,b,c)$。

共 $q$ 行，每行一个数，为对于每个三元组的 $i$ 的个数。

--- #### 样例 2 解释  第一个查询的 $i$ 为 $3$ 和 $4$。 第二个查询的 $i$ 为 $1$。 --- #### 数据范围 #### 本题按子任务测试： - Subtask 1（$20$ pts）：$1 \leq n \leq 1000$，$1 \leq q \leq 500$。 - Subtask 2（$15$ pts）：$1 \leq n \leq 10^{5}$，$1 \leq q \leq 10^{5}$，树退化成链。 - Subtask 3（$25$ pts）：$1 \leq n \leq 5 \times 10^{5}$，$1 \leq q \leq 10^{5}$，数据**不随机**。 - Subtask 4（$40$ pts）：$1 \leq n \leq 5 \times$ $10^{5}$，$1 \leq q \leq 2 \times 10^{5}$。 对于所有数据：$1 \leq n \leq 5 \times 10^{5}$，$1 \leq q \leq 2 \times 10^{5}$。 注：数据强度不高，不必卡常与快读快输。