Counting C-Blocks in a Tree

You are given a tree with n nodes labelled from 1 to n and with every edge having a weight of 1. You are also given an integer constant C.

Define \(dist(a,b)\) as the distance between nodes \(a\) and \(b\) in the tree, i.e. the sum of the weights on the unique simple path between \(a\) and \(b\) (with \(dist(a,a)=0\)).

For each query, you are given an interval \([l, r]\) (with \(1 \le l \le r \le n\)). In the current query, consider the set of nodes \(V = {l, l+1, \dots, r}\). Define two nodes \(a, b \in V\) to be C-connected if and only if there exists a sequence of nodes \(\{v_i\}_{i=1}^t\) such that:

• \(v_1 = a\) and \(v_t = b\);
• For every \(1 \le i \le t-1\), \(dist(v_i,v_{i+1}) \le C\);
• For every \(1 \le i \le t\), \(v_i \in V\) (i.e. \(l \le v_i \le r\)).

A subset \(S \subseteq V\) is called a C-block if:

1. For every \(a \in S\) and every \(b \in V \setminus S\), \(a\) and \(b\) are not C-connected;
2. For every \(a, b \in S\), \(a\) and \(b\) are C-connected;
3. Every element \(a \in S\) satisfies \(l \le a \le r\).

Your task is, for each query, to count the number of C-blocks among the nodes in \([l, r]\). Note that the connectivity is defined solely by the condition that two nodes \(a\) and \(b\) (with \(a, b \in [l, r]\)) have a "jump" if \(dist(a, b) \le C\); such a jump can be taken regardless of the nodes that lie on the unique tree path between them.

Input Format: The first line contains three integers \(n, C, Q\). The next \(n-1\) lines each contain two integers \(u\) and \(v\), indicating an edge between nodes \(u\) and \(v\) in the tree. Then \(Q\) lines follow, each containing two integers \(l\) and \(r\), representing a query.

Output Format: For each query, output one integer on a new line, representing the number of C-blocks in the subgraph induced by the nodes in \([l, r]\) with an edge between any two nodes if and only if \(dist(u,v) \le C\).

inputFormat

The input begins with a single line containing three integers \(n\) (the number of nodes), \(C\) (the connectivity constant), and \(Q\) (the number of queries).

The next \(n-1\) lines each contain two integers \(u\) and \(v\), denoting an undirected edge in the tree.

Then \(Q\) lines follow, each containing two integers \(l\) and \(r\) representing a query.

Constraints: It is guaranteed that the given graph is a tree. You may assume that \(n\) is small enough (for example, \(n \leq 300\)) such that an \(O(n^2)\) solution is feasible.

outputFormat

For each query, output a single integer on a new line — the number of C-blocks in the subgraph induced by nodes in the interval \([l, r]\).

sample

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

1
1
1

</p>