Path containing K Nodes  Problem code: KNODES

SUBMIT MY SUBMISSIONS ALL SUBMISSIONS

All submissions for this problem are available.

Read problems statements in Mandarin Chinese and Russian as well.

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.

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).

                 ******************  THE CODE GOES HERE **************************************************

#include<bits/stdc++.h>

using namespace std;

list<int> arr[100010];

#define mp make_pair

#define pb push_back

#define ff first

#define ss second

int tmi=0;

int level[100010];

int T[100010];

int dp[100010][25];

int n;

int sttime[100010];

int ettime[100010];

void pre()

{

   memset(dp,-1,sizeof(dp));

   //cout<<"here "<<endl;

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

   {

     dp[i][0]=T[i];

 //    cout<<"set  oth ancestor of "<<i<<" as "<<T[i]<<endl;

}

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

{

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

  {

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

     {

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

}

  }

}

}

int flca(int p, int q)

{

//cout<<"levels "<<level[p]<<" "<<level[q]<<endl;

  if(level[p]<level[q])

  {

   swap(p,q);

  }

  int log;

  for(log=1;(1<<log)<=level[p];log++);

  log--;

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

          if (level[p] - (1 << i) >= level[q])

              p = dp[p][i];

   

      if (p == q)

          return p;

        //  cout<<"log  is "<<log<<endl;

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

           {

     // cout<<"to chek "<<i<<" th ancestor of "<<p<<" "<<q<<" they are "<<dp[p][i]<<" "<<dp[q][i]<<endl;

          if (dp[p][i] != -1 && dp[p][i] != dp[q][i])

          {

 

              p = dp[p][i], q = dp[q][i];

              //   cout<<"change p q to "<<p<<" "<<q<<endl;

}

             }

      return T[p];

}

void dfs(int root,int par,int lev)

{

 level[root]=lev;

 sttime[root]=tmi;

 T[root]=par;

 list<int> ::iterator it;

  for(it=arr[root].begin();it!=arr[root].end();it++)

     { 

         if(*it!=par)

 {

          tmi++;

  dfs(*it,root,lev+1);

 }  

 }

 ettime[root]=tmi;

}

bool ischild(int ch,int an)

{

      if(sttime[ch]>=sttime[an] && ettime[ch]<=ettime[an])

      return 1;

      return 0;

}

int main()

{

int t;

cin>>t;

while(t--)

{

     

 //int n;

 tmi=0;

 cin>>n;

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

 arr[i].clear();

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

 {

   int aa,bb;

   scanf("%d %d",&aa,&bb);

   arr[aa].pb(bb);

   arr[bb].pb(aa);

 }

 dfs(1,0,0);

 pre();

 int q;

 cin>>q;

 while(q--)

 {

      int tt;

      scanf("%d",&tt);

      vector<int> v;

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

      {

       int aa;

       scanf("%d",&aa);

       v.pb(aa);

      // mark[i]=0;

}

vector<int> a,b,c,d,e;

int lev=0;

int deep1=0;

int lvmi=1000000;

int sm=-1;

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

{

    if(level[v[i]]>lev)

    {

      deep1=v[i];

      lev=level[deep1];

}

if(level[v[i]]<lvmi)

{

 sm=v[i];

 lvmi=level[sm];

}

}

// cout<<"deep 1 "<<deep1<<endl;

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

{

 int nd=v[i];

if(sttime[nd]<=sttime[deep1] && ettime[nd]>=ettime[deep1])

{

     a.pb(nd);

//      cout<<"in a "<<nd<<endl;

 }

 else

 {

   b.pb(nd);

 }

}

if(b.size()==0)

{

 printf("Yes\n");

 continue;

}

int sz=b.size();

lev=0;

int deep2=-1;

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

{

     int nd=b[i];

 if(level[nd]>lev)

 {

   lev=level[nd];

      deep2=nd;  

 }

}

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

{

   int nd=b[i];

if(sttime[nd]<=sttime[deep2] && ettime[nd]>=ettime[deep2])

{

     c.pb(nd);

//      cout<<"in a "<<nd<<endl;

 }

 else

 {

   d.pb(nd);

 }

}

if(d.size()!=0)

{

 printf("No\n");

 continue;

}

    int res=c.size();

int lca=flca(deep2,deep1);

if(ischild(sm,lca))

{

 printf("Yes\n");

 

}

else printf("No\n");  

}

// cout<<"deep2 "<<deep2<<endl;

 

      }

      return 0;

      

}