30073 - 树上询问
时间限制 : 1 秒
内存限制 : 128 MB
给定一棵 n 个点的无根树，有 q 次询问。
每次询问给一个参数三元组 (a,b,c)，求有多少个 i 满足这棵树在以 i 为根的情况下 a 和 b 的 LCA 为 c。
输入
第一行 2 个数，为 n 和 q。
接下来 n-1 行，每行 2 个数，表示树的一条边。
接下来 q 行，每行 3 个数，为 (a,b,c)。
输出
共 q 行，每行一个数，为对于每个三元组的 i 的个数。
样例
输入
10 5 1 2 1 3 2 4 2 5 2 10 5 6 3 7 7 8 7 9 4 6 2 4 10 1 6 8 3 9 10 2 4 10 5
输出
7 0 1 4 0
输入
5 3 1 3 1 5 3 4 3 2 5 2 3 5 2 1 2 4 5
输出
2 1 0
输入
20 10 1 2 1 3 1 4 2 5 2 6 3 10 4 13 4 14 6 7 6 8 10 11 4 15 4 16 8 9 11 12 16 17 16 18 16 19 17 20 15 19 16 1 12 1 20 20 20 7 7 8 1 8 3 5 20 2 2 9 6 9 12 1 9 12 2 9 12 3
输出
4 16 20 0 0 5 2 10 2 1
提示
对于所有数据：1 \le n \le 5 \times 10^5，1 \le q \le 2 \times 10^5。