Tree Intersection Query

5

2 votes
Algorithms, Graphs, Binary Search, Depth First Search
Problem

You are given a tree consisting of N nodes. You have to answer Q queries. The qth query consists of a node xq and a set of kq distinct nodes {v1,v2,,vkq}. The answer to the  qth query is the number of pairs (i,j) such that 1i<jkq and the node xq lies on the path between the nodes vi and vj.

Input format

  • The first line of input contains two integers N denoting the number of nodes in the tree and Q denoting the number of queries.
  • N1 lines follow. The ith line contains two integers Xi,Yi denoting an edge between the nodes Xi,Yi. It is guaranteed that the given nodes and edges form a tree.
  • 2Q lines follow. The (2q1)-th of these lines contains two integers xq,kq, and the 2q -th line contains kq space-separated distinct integers {v1,v2,,vkq}.

Output format

For each query, print the answer in a separate line.

Constraints

2N21051Q21051Xi<YiN1kq,xq,vqNkq3.5105

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

In the first query, the paths which contain node 3 are 15,18,25,28,58.

In the second query, the paths which contain node 2 are 24,26.

 

Editor Image

?