P6374 "StOI-1" Tree Queries

Given an unrooted tree with $n$ nodes, there are $q$ queries. Each query provides a parameter triple $(a,b,c)$. You need to find how many nodes $i$ satisfy that, when the tree is rooted at $i$, the [LCA](https://www.luogu.com.cn/problem/P3379) of $a$ and $b$ is $c$.

The first line contains $2$ integers, $n$ and $q$. The next $n-1$ lines each contain $2$ integers, describing an edge of the tree. The next $q$ lines each contain $3$ integers, which are $(a,b,c)$.

Output $q$ lines. Each line contains one integer: for each triple, the number of valid nodes $i$.

--- #### Explanation for Sample 2  For the first query, the valid $i$ are $3$ and $4$. For the second query, the valid $i$ is $1$. --- #### Constraints #### This problem is tested by subtasks: $subtask1 (20pts)$: $1 \leq n \leq 1000$, $1 \leq q \leq 500$. $subtask2 (15pts)$: $1 \leq n \leq 10^{5}$, $1 \leq q \leq 10^{5}$, the tree degenerates into a chain. $subtask3 (25pts)$: $1 \leq n \leq 5 \times 10^{5}$, $1 \leq q \leq 10^{5}$, the testdata is **not random**. $subtask4 (40pts)$: $1 \leq n \leq 5 \times 10^{5}$, $1 \leq q \leq 2 \times 10^{5}$. For all testdata: $1 \leq n \leq 5 \times 10^{5}$, $1 \leq q \leq 2 \times 10^{5}$. Note: the testdata is not very strong, so there is no need to micro-optimize or use fast input/output. Translated by ChatGPT 5