Chef and Pairs | PAIRCNT | CODECHEF JULY CHALLENGE

Codechef

View problem on codechef

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

Each query is of the form:

  • K D V1 V2 ⋯ VKK D V1 V2 ⋯ VK – output the number of pairs (i,j)(i,j), 1≤i<j≤K1≤i<j≤K, such that the shortest path between nodes ViVi and VjVj in the tree has DD edges.
For the work from home Internship Programs : Click here to apply now

Input

  • The first line contains an integer TT, the number of test cases. Then the test cases follow.
  • The first line of each test case contains two integers, NN and QQ.
  • N−1N−1 lines follow. Each line consists of two integers uu and vv, indicating that there is an edge between nodes uu and vv in the tree.
  • QQ 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≤51≤T≤5
  • 1≤N,Q≤1051≤N,Q≤105
  • 1≤u,v,Vi≤N1≤u,v,Vi≤N
  • 0≤D≤1050≤D≤105
  • The sum of KK across all queries in a single test case is at most 105105.

Subtasks

  • Subtask 1 (20 points): For each query, K≤10K≤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)(2,3) and (2,5)(2,5) have distance 22.

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

SOLUTION

Due to copyright issues we won't be able to update the solution here immediately. However you can download the code file from our telegram channel. So join our telegram channel for further updates. Keep tracking, the solution will be updated on this website soon.

Read More Post Here

Leave a Comment

Your email address will not be published. Required fields are marked *

x