시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 0 0 0 0.000%

문제

Alice and Bob like to play games on a tree with $n$ vertices conveniently labeled with $1, 2, \dots, n$. They play a total of $q$ games.

In game $i$, Alice starts at vertex $a_i$ while Bob starts at a different vertex $b_i$. Initially, all vertices have no color except for the vertices $a_i$ and $b_i$: vertex $a_i$ is colored by Alice while vertex $b_i$ is colored by Bob.

After that, the players take turns for $k_i$ moves in total: Alice moves first, Bob moves second, then Alice makes the third move, and so on. In each move, the respective player moves to an adjacent vertex and colors it. Note that a vertex can be recolored: at any moment, each colored vertex has the color of the player who arrived there most recently.

Let the final number of vertices of Alice's color be $A$, and the final number of vertices of Bob's color be $B$. Alice would like to maximize the number $(A - B)$, while Bob would like to minimize this number.

For each game, find the difference $(A - B)$ if both players play optimally.

입력

The input contains zero or more test cases, and is terminated by end-of-file. For each test case:

The first line contains two integers $n$ and $q$ ($2 \leq n \leq 2 \cdot 10^5$, $1 \leq q \leq 2 \cdot 10^5$).

The $i$-th of the following $(n - 1)$ lines contains two integers $u_i$ and $v_i$ which denote an edge between vertices $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq n$). It is guaranteed that the input forms a tree.

The $i$-th of the last $q$ lines contains three integers $a_i$, $b_i$ and $k_i$ ($1 \leq a_i, b_i \leq n$, $1 \leq k_i \leq 2 n$, $a_i \neq b_i$). It is guaranteed that both the sum of all $n$ and the sum of all $q$ do not exceed $2 \cdot 10^5$.

출력

For each test case, output an integer which denotes the difference.

예제 입력 1

4 3
1 2
2 3
3 4
1 4 1
1 4 2
1 4 3

예제 출력 1

1
0
2