Chef and Pairs | CodeChef Solution

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

Chef and Pairs | CodeChef Solution

Contents

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 V1 V2 . . . VK – output the number of pairs ( i, j ), 1 ≤ i < jK, such that the shortest path between nodes Vi and Vj 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 ≤ 105
  • 1 ≤ u, v,ViN
  • 0 ≤ D ≤ 105
  • The sum of K across all queries in a single test case is at most 105.

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.

Leave a Comment

Your email address will not be published.