Chef and Pairs | CodeChef Solution

Hello coders, today we are going to solve Chef and Pairs CodeChef Solution whose Problem Code is PAIRCNT.

Task

You are given a tree (connected, undirected, acyclic graph) consisting of N nodes. Based on this tree, you have to answer Q queries.

Each query is of the form:

• K D V₁ V₂ . . . V_K – output the number of pairs ( i, j ), 1 ≤ i < j ≤ K, such that the shortest path between nodes V_i and V_j in the tree has D edges.

Input

• The first line contains an integer T, the number of test cases. Then the test cases follow.
• The first line of each test case contains two integers, N and Q.
• N − 1 lines follow. Each line consists of two integers u and v, indicating that there is an edge between nodes u and v in the tree.
• Q lines follow. Each line describes a query in the format given above.

Output

For each query, output the answer on a new line.

Constraints

• 1 ≤ T ≤ 5
• 1 ≤ N, Q ≤ 10⁵
• 1 ≤ u, v,V_i ≤ N
• 0 ≤ D ≤ 10⁵
• The sum of K across all queries in a single test case is at most 10⁵.

Subtasks

Subtask 1 (20 points): For each query, K ≤ 10
Subtask 2 (80 points): Original constraints

Sample Input

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

Sample Output

2
0

Explanation

In the first query, the pairs of nodes (2, 3) and (2, 5) have distance 2.

In the second query, there is no pair with distance 4.

Solution – Chef and Pairs

C++

Python

Java

Disclaimer: The above Problem (Chef and Pairs) is generated by CodeChef but the Solution is Provided by CodingBroz. This tutorial is only for Educational and Learning Purpose.