*****Path containing K Nodes ( given k number of nodes find wether all these nodes lies in a single path or not )

Path containing K Nodes 

You are given a tree.

You have to execute numerous queries on this tree. In a query, you will be given K nodes and you need to find if there is a path in the tree which contains all these K nodes.

If there is a path containing these K nodes, then output Yes. Otherwise, output No.

Input

First line contains T, number of test cases to follow.

First line of each test case contains an integer N which represents the number of nodes in the tree.

Next N-1 lines contain the description of the tree. Each line contains 2 space separated integers implying that there is an edge between these two nodes.

Next line contains Q, number of path queries to follow.

First line of each query contains an integer K.

Second line contains K space separated nodes.

Output

For each query, output Yes if there is a path containing the K query nodes. Otherwise, output No.

Constraints

• 1 ≤ N ≤ 10⁵
• 1 ≤ Sum of N over all test cases ≤ 10⁵
• 1 ≤ T ≤ 500
• 3 ≤ K ≤ N
• 1 ≤ Sum of K over all test cases and queries ≤ 10⁶
• Nodes are numbered from 1

Example

Input:

1
10
3 1
5 7
4 6
10 4
8 9
2 1
3 4
8 5
5 3
4
3
8 10 3
4
8 7 9 6
3
2 1 6
3
6 2 5

Output:

Yes
No
Yes
No

Explanation:

Query 1: The path corresponding to it is 8->5->3->4->10.

Query 2: There does not exists any path joining all 4.

-----------------------------EDITORIAL----------------------------------

THIS PROBLEM CAN BE SOLVED IN MANY DIFFERENT WAYS 

1ST WAY 

Fix any node as root of the tree. Then do a depth-first traversal and store 3 things for each node:

1. Depth of the node : It is the distance of the node from the root  and also set parent of each node .
2. now find kth( k in terms of log, 2^k )  parent of each node  using dp.
3.  write a function lca(a,b) which will return lca of a and b 
4. now  for any query initially insert all nodes in set pair <int,int> first parameter will be the depth and the second parameter will  the  node 
5.   we can consider node with the minimum depth as the meeting point of the path two path 
6. now take  node from the set with maximum dept set a  and find lca of  with all nodes which are present in the set , let say other node is b if lca (a,b)==b  than remove this node from the set , since these 2 nodes are in the same path (same line )  
7. if after this operation set is empty than ans is yes , else
8. take another node  from the set with the max depth and do sam process as before .....
9. now if set is empty and lca(1st node chosed , 2nd node chosed )  have level< than the  minimum level of all nodes  out of k nodes than ans will be yes (  since both nodes chosen must meet a the node with minimum level in the given set or any other node with  levee less that that of the node with minimum level from k nodes  than only path b/w two chosen nodes can cover all nodes else not .... draw an example to understand this )   ex suppose connection of raph is like 1-2 ,  2-3 , 2- 4 and if we chose nodes 1 , 3 ,4 than  in first step we chose deepest node as node 3 and in 2nd step we chose node 4 after operating on these two nodes , all nodes from the set  will pop out , but still there is no simple path cover all these nodes , since lca(3,4) is 2    but node 1 is in the set of k nodes have level <  node 2 ......
10. else ans is no 

also read second approach ..  

--------------------------code --------------------------first approach ---------------------------------------------------------

#include<bits/stdc++.h>

using namespace std;

list<int> li[1000000];

int used[10000000];

int dp[100010][30];

int lev[1000000];

#define pb push_back

int dfs(int start,int p,int le)

 {

      lev[start]=le;

     list<int>::iterator it;

     for(it=li[start].begin();it!=li[start].end();it++)

      {

      if(*it!=p)

       {

        dp[*it][0]=start;        

        dfs(*it,start,le+1);

}

 }

 }

 

 

 

 

int lca(int a,int b)

 {

   if(lev[a]<lev[b]) swap(a,b);

   

   int lg;

   

   

   for(lg=1;(1<<lg)<=lev[a];lg++);

   

   

   lg--;

   

   

     for(int i=lg;i>=0;i--)

      {

        if(lev[a]-(1<<i)>=lev[b])

         {

            a=dp[a][i];

          }

      }

    

   

    

   if(a==b) return a;

   

   else

   {

    for(int i=lg;i>=0;i--)

    {

     if(dp[a][i]!=-1 && dp[a][i]!=dp[b][i]) 

      {

        a=dp[a][i];

        b=dp[b][i];

      }

    }

   

    

    return dp[a][0];

   }

 }

int main()

 {

  int t;

   cin>>t;

  while(t--)

   {

      memset(dp,-1,sizeof dp);

    int n;

    cin>>n;

    for(int i=0;i<=n;i++) li[i].clear();

    for(int i=0;i<n-1;i++)

       {

      int a,b;

      scanf("%d %d",&a,&b);

      li[a].pb(b);

      li[b].pb(a);

}

 

dp[1][0]=-1;

dfs(1,-1,1);

for(int i=1;i<30;i++)

 {

  for(int j=0;j<=n;j++)

  {

  if(dp[j][i-1]!=-1)

  dp[j][i]=dp[dp[j][i-1]][i-1];

  }

 }

int q;

 cin>>q;

 while(q--)

  {

   int k; 

scanf("%d",&k);

      int mini=10000000;

       set<pair<int,int> > s;

       vector<int> v;

        for(int i=0;i<k;i++)

         {

            int a;

          scanf("%d",&a);

            s.insert({lev[a],a});

            v.push_back(a);

            mini=min(mini,lev[a]);

}

 int start=s.rbegin()->second;

 vector<int> vv;

 int lf1=start;

 for(int i=0;i<k;i++)

  {

  int lc=lca(start,v[i]);

  

  if(lc==start || lc==v[i])

   {

       

 

    if(s.find({lev[v[i]],v[i]})!=s.end())

     {

     

      s.erase({lev[v[i]],v[i]});

  }

}

else vv.pb(v[i]);

  }

  if(s.empty())

    printf("Yes\n");

   else

   {

      start=s.rbegin()->second;

     

      s.erase({lev[start],start});

      int lf2=start;

      k=vv.size();

     for(int i=0;i<k;i++)

      {

       int lc=lca(start,vv[i]);

 

      if(lc==start || lc==vv[i])

       {

     

        if(s.find({lev[vv[i]],vv[i]})!=s.end())

         {

         s.erase({lev[vv[i]],vv[i]});

  }

}

       }

       

      

       if(s.size()==0  && lev[lca(lf1,lf2)]<=mini)

        {

         printf("Yes\n");

}

else  printf("No\n");

}

 

 

  }

 

   }

 }

-------------------------------------------SECOND APPROACH--------------------------------------------------------------

DIFFICULTY:

Medium

PREREQUISITES:

DFS

PROBLEM:

You are given a tree. You need to process Q$Q$ queries. Each query gives you K$K$ nodes and you need to print "Yes" if there is a path connecting them, and "No" otherwise.

Quick Explanation:

We will try building a path to solve this problem. A path will have 2$2$ end points and we will first try to find out these two end points (say D$D$ and RD$RD$) and then try to check if all the nodes lie either on the path from D$D$ to the root or from RD$RD$ to root.

Now, if the above conditions are satisfied, we need to check whether they still form a pair or not. Solution contains a detailed explanation of the approach.

Solution:

Fix any node as root of the tree. Then do a depth-first traversal and store 3 things for each node:

1. Depth of the node : It is the distance of the node from the root.
2. Start time of the dfs : It is the time when the dfs started on the node.
3. End time of the dfs : It is the time when the dfs ended on the node.

You can increase time by 1$1$ when moving to an unvisited node.

Now for all the given K$K$ nodes, find the deepest node and the node closest to root.

Let the deepest node be D$D$ and let the node closest to root be S$S$.

We will now partition the set of K$K$ nodes into two disjoint sets A$\mathbf{A}$ and B$\mathbf{B}$.

Set A$\mathbf{A}$ will contain nodes which are on the path from root to D$D$. Set B$B$ will contain the remaining nodes.

How to make set A$\mathbf{A}$?

If the start time of node X$X$ is before the start time of node D$D$ and the end time of node X$X$ is after the end time of node D$D$ then node X$X$ belongs to set A$\mathbf{A}$. [Using properties of DFS]

If set B$\mathbf{B}$ was a null set, then our answer is "Yes".

Find the deepest node in the set B$\mathbf{B}$, let us name it as RD$RD$. [Deepest node in the remaining nodes/set B$\mathbf{B}$]

Now again follow the same procedure to partition the set B$\mathbf{B}$ into C$\mathbf{C}$ and E$\mathbf{E}$ where set C$\mathbf{C}$ contains nodes from set B$\mathbf{B}$which are on the path from RD$RD$ to root of the tree.

If set E$\mathbf{E}$ is not empty, then our answer is "No". ( Reasons ? : I hope the readers to use pen and paper to draw a diagram and understand how things are moving, from there it will be trivial to find the reason)

Now, Find the LCA of D$D$ and RD$RD$. Let us call this node as L$L$.

L$L$ must lie between S$S$ (smallest depth node in K$K$ nodes) and root of the tree for a valid path to exists.

Reason:

If S$S$ lies in between root and L$L$, then there does not exist any path.

L$L$ must be repeated twice in the journey from D$D$ to RD$RD$. Hence not a path.

Time complexity of this algorithm is O(N)$\mathcal{O}(N)$ (for dfs part per test case) + O(K+log(N))$\mathcal{O}(K+log(N))$ (per query).

-----------------------------------------------------CODE-----------------------------------------------------------------------------

#include<stdio.h>
#include<iostream>
#include<vector>
#include<string.h>
#include<string>
#include<stdlib.h>
#include<algorithm>
#include<set>
#include<stack>
#include<queue>
#include<assert.h>
#include<utility>
using namespace std;
typedef long long int ll;

#define mp	make_pair
#define pb push_back
#define MaxN 100009

vector<int> graph[MaxN];

/*************LCA Part is Here****************/
int Root[MaxN][18],log2[MaxN],depth[MaxN],start[MaxN],end[MaxN],parent[MaxN],counter,visited[MaxN];
void init()
{
	log2[0]=0;log2[1]=0;log2[2]=1;
	int cmp=4;
	for(int i=3;i<=100000;i++){
		if(cmp>i) log2[i]=log2[i-1];
		else{
			log2[i]=log2[i-1]+1;
			cmp<<=1;
		}
	}
}
void get2p(int N)
{
	memset(Root,-1,sizeof(int)*18*(N+1));
	for(int i=1;i<=N;i++)
		Root[i][0]=parent[i];
	for(int i=1;(1<<i)<=N;i++)
		for(int j=1;j<=N;j++)
			if(Root[j][i-1]!=-1)
				Root[j][i]=Root[Root[j][i-1]][i-1];
}
int lca(int p,int q)
{
	int temp;
	//first we make q the more deeper node
	if(depth[p]>depth[q])
		swap(p,q);
	//we find the closest power of 2
	int steps=log2[depth[q]];
	//we try to make the depth of q equal to p and then increase both
	for(int i=steps;i>=0;i--)
		if((depth[q]-(1<<i)) >= depth[p])
			q=Root[q][i];
	//if p was equal to q at the time of depth balancing then it is indeed a ancestor
	if(p==q)
		return p;
	//now we increase both p and q by small amount and if value is different , then we procede up
	for(int i=steps;i>=0;i--){
		if(Root[p][i]!=Root[q][i])
			p=Root[p][i],q=Root[q][i];
	}
	//we end up getting 1 node short for parent.
	return parent[p];
}
void LCA(int N)
{
	//if you have parent and depth stored
	get2p(N);
}
/*************************LCA part Ends********************/

void dfs(int root)
{
	visited[root] = 1;
	counter++;
	for(int i=0;i<graph[root].size();i++){
		int v = graph[root][i];
		if( visited[v] )	continue;
		else{
			depth[v] = depth[root] + 1;
			parent[v] = root;
			start[v] = counter;
			dfs(v);
		}
	}
	end[root] = counter;
}


void solve()
{
	int N;
	char tst;
	scanf("%d",&N);

	for(int i=1;i<=N;i++)	graph[i].clear(),visited[i] = 0;
	for(int i=1;i<N;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		graph[x].pb(y);
		graph[y].pb(x);
	}
	counter = 0;
	depth[1] = 1;
	parent[1] = -1;
	dfs(1);
	LCA(N);
	int Q,k,max_depth_node,max_d,smallest_depth_node,small_d;
	scanf("%d",&Q);
	//printf("%d is Q\n",Q);
	for(int i=1;i<=Q;i++){
		max_d = 0;
		small_d = 1e9;
		vector<int> nodes;
		scanf("%d",&k);
		for(int j=0;j<k;j++){
			int x;
			scanf("%d",&x);
			if( depth[x] > max_d ){
				max_d = depth[x];
				max_depth_node = x;
			}
			if( depth[x] < small_d ){
				small_d = depth[x];
				smallest_depth_node = x;
			}
			nodes.pb(x);
		}
		//printf("%d %d %d %d\n",max_depth_node,max_d,smallest_depth_node,small_d);
		int diff = -1,flag=1,remaining_maximum_depth_node,rem_max_d=0;
		for(int j=0;j<k;j++){
			int u = nodes[j];
			if( start[u]<=start[max_depth_node] && end[u]>=end[max_depth_node] ){
				continue;
			}
			else{
				flag = 0;
				if( depth[u] > rem_max_d){
					rem_max_d = depth[u];
					remaining_maximum_depth_node = u;
				}
			}
		}

		if( flag ){
			printf("Yes\n");
			continue;
		}

		int print = 0;
		for(int j=0;j<k;j++){
			int u = nodes[j];
			if( start[u]<=start[max_depth_node] && end[u]>=end[max_depth_node] ){
				continue;
			}
			else if( !(start[u]<=start[remaining_maximum_depth_node] && end[u]>=end[remaining_maximum_depth_node]) ){
				printf("No\n");
				print = 1;
				break;
			}
		}
		if( print == 0 ){
			int x = lca(max_depth_node,remaining_maximum_depth_node);
			if( start[smallest_depth_node] >= start[x] && end[smallest_depth_node] <= end[x] ){
				printf("Yes\n");
			}
			else{
				printf("No\n");
			}
		}
	}
}

int main()
{
	init();
	char tst;
	int T;
	scanf("%d",&T);
	for(int i=1;i<=T;i++){
		solve();
	}
	return 0;
}