Description

One day, Xiao S and her friend Xiao N studied a tree with $n$ nodes.

This is a rooted tree with root node numbered $1$. The depth $\text{dep}_u$ of a node $u$ is defined as the number of nodes on the simple path from $u$ to $1$.

Additionally, $\text{LCA*}(l, r)$ is defined as the lowest common ancestor (LCA) of all nodes with numbers in $[l, r]$, i.e., the deepest node that is an ancestor of all nodes $l, l + 1, \dots, r$.

Xiao N posed $q$ queries about this tree. For each query, he provides three parameters $l, r, k$, asking for the maximum depth among the LCAs of all continuous subintervals of $[l, r]$ with length at least $k$. Formally, compute:

$$\max_{l\le l'\le r'\le r \land r'-l'+1\ge k}\text{dep}_{\text{LCA*}(l', r')}$$

Your task is to help Xiao S answer these queries.

Input Format

The first line contains a positive integer $n$, the number of nodes in the tree.

The next $n - 1$ lines each contain two positive integers $u$ and $v$, representing an edge between nodes $u$ and $v$.

The $(n + 1)$-th line contains a positive integer $q$, the number of queries.

The next $q$ lines each contain three positive integers $l, r, k$, describing a query.

Output Format

For each query, output one line containing the answer.

6
5 6
6 1
6 2
2 3
2 4
3
2 5 2
1 4 1
1 6 3

3
4
3

Hint

Explanation

【Sample 1 Explanation】

$\text{Pic 3: The tree in sample 1}$

• For the first query:

  • $\text{LCA*}(2, 3) = 2$, $\text{LCA*}(3, 4) = 2$, $\text{LCA*}(4, 5) = 6$.
  • The depth of node $2$ is $3$, and the depth of node $6$ is $2$.
  • Thus, the answer is $\max\{3, 3, 2\} = 3$.

• For the second query:

  • The answer is the maximum depth among nodes $1, 2, 3, 4$, which is $4$.

• For the third query:

  • $\text{LCA*}(1, 3) = 1$, $\text{LCA*}(2, 4) = 2$, $\text{LCA*}(3, 5) = 6$, $\text{LCA*}(4, 6) = 6$.
  • The depth of node $2$ is $3$, which remains the maximum, so the answer is $3$.

【Sample 2】

See the attached files query/query2.in and query/query2.ans.

This sample satisfies $n, q \leq 500$.

【Sample 3】

See the attached files query/query3.in and query/query3.ans.

This sample satisfies $n, q \leq 10^5$ and the tree forms a chain.

【Sample 4】

See the attached files query/query4.in and query/query4.ans.

This sample satisfies $n, q \leq 5 \times 10^5$.

【Data Range】

For all test data:

• $1 \leq n, q \leq 5 \times 10^5$
• $1 \leq l \leq r \leq n$
• $1 \leq k \leq r - l + 1$

Test Case Range	$n, q \leq$	Special Constraints
$1\sim2$	$500$	None
$3\sim5$	$5000$
$6\sim9$	$10^5$	Property A
$10\sim13$	$5 \times 10^5$
$14\sim16$		Property B
$17\sim20$	$10^5$	None
$21\sim25$	$5 \times 10^5$

• Property A: The tree is a chain (root has degree $1$).
• Property B: For every query, $k = r - l + 1$.

---

Translated by DeepSeek R1