K Path Query Codechef Solution

K Path Query Codechef Solution

You’re given a tree with NN vertices numbered from 11 to NN. Your goal is to handle QQ queries. For each query you are given KK nodes v1,v2,…,vKv1,v2,…,vK. Find if there exists a simple path in the tree covering all the given vertices.

See Also : July Long Challenge 2021 Solutions Codechef

Input

• The first line contains a single integer TT – the number of test cases. The description of TT test cases follows.
• The first line of each test case contains a single integer NN.
• Each of the following N−1N−1 lines contains two integers uu and vv denoting an edge between nodes uu and vv.
• The next line contains a single integer QQ – the number of queries.
• The next QQ lines describe queries. The ii-th line describes the ii-th query and starts with the integer KiKi — the number of vertices in the current query. Then KiKi integers follow: v1,v2,…,vKiv1,v2,…,vKi.

Output

For each query print "YES" (without quotes) if there exists a simple path in the tree covering all the given nodes, otherwise print "NO" (without quotes).

You may print each character of the string in uppercase or lowercase (for example, the strings "yEs", "yes", "Yes" and "YES" will all be treated as identical).

Constraints

• 1≤T≤101≤T≤10
• 1≤N≤1051≤N≤105
• 1≤u,v,vj≤N1≤u,v,vj≤N
• 1≤Q≤1051≤Q≤105
• 1≤Ki≤N1≤Ki≤N for each valid ii.
• The edges form a valid tree.
• All vertices in a single query are distinct.
• the sum of NN over all test cases does not exceed 2⋅1052⋅105.
• For each test case, the sum of KiKi over all queries does not exceed 105105.

Subtasks

Subtask #1 (100 points): Original constraints

Sample Input

1
6
1 2
1 3
2 4
2 5
3 6
2
3 6 2 4
4 2 3 4 5

Sample Output

YES
NO

Explanation

The structure of the given tree is shown below. 

• For the first query the path will be 4−2−1−3−64−2−1−3−6.
• For the second query there is no simple path that covers all the given vertices.

Solution

Program Java:

Credit : Mohammad Asif
import java.util.*;
public class KpathQuery {

  public static void main(String[] args){

  Scanner sc = new Scanner(System.in);
  int tt = sc.nextInt();
 while(tt-->0)
 {

    int I = Integer.MAX_VALUE;
    int n = sc.nextInt();
    int [][] cost= new int [n][n];
     

// near 
  
     int near[] = {I,I,I,I,I,I,I,I};
     
     int [][] t = new int [2][6];
     int i,j,n=7,min=I;
     int k=0;

     int u =-1;
     int v = -1;
     // find the min value from the upper triangular matrix 
     for(i = 1; i <=n; i++){
       for (j = i; j <=n; j++) {
         if(cost[i][j] < min){
           min = cost[i][j];
          u = i;
          v = j;
         }

         
       }
     }
      t[0][0] = u;
      t[1][0] = v;
      near[u] = 0;
      near[v] = 0;

      for(i =1; i<=n; i++){
        if(near[i]!=0) {
        if(cost[i][u] <cost[i][v])
          near[i] = u;
        else
          near[i] = v;
      }
      }
     
    for(i = 1; i <n-1; i++){
      min = I;

      for(j = 1; j <=n; j++){
        if(near[j]!=0 && cost[j][near[j]] < min ){
          k = j;
          min = cost[j][near[j]];
        }
      }
      t[0][i] = k;
      t[1][i] = near[k];
      near[k] = 0;

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

        if(near[j]!=0 && cost[j][k] < cost[j][near[j]])
          near[j] = k;
      }
    }
  for(i = 0; i <n-1; i++){
    System.out.println(t[0][i]+" "+t[1][i]);
  }
  }
}


}

Program Java:

Credit: Here
import java.util.*;
import java.lang.*;
import java.io.*;

class Codechef {
 public static void main (String[] args) throws java.lang.Exception {
 
  Scanner sc = new Scanner(System.in);
 
  int T = sc.nextInt();
 
  while(T-- > 0) {
   int N = sc.nextInt();
   Map<Integer, Set<Integer>> tree = new HashMap<>();
   for(int i = 1; i < N; i++) addPath(tree, sc.nextInt(), sc.nextInt());
 
            int[] level = new int[N+1];
            int[] parent = new int[N+1];
   preProcess(tree, level, parent);
 
   int Q = sc.nextInt();
   int[] visited = new int[N+1];
   for(int i = 1; i <= Q; i++) {
    int K = sc.nextInt();
    int[] query = new int[K];
    int maxDepth = 0;
    int nodeWithMaxDepth = -1;
    for(int j = 0; j < K; j++) {
     query[j] = sc.nextInt();
     if(level[query[j]] > maxDepth) {
      maxDepth = level[query[j]];
      nodeWithMaxDepth = query[j];
     }
    }
 
    boolean hasPath = process(nodeWithMaxDepth, parent, level, query, visited, i);
    System.out.println(hasPath ? "YES" : "NO");
   }
  }
 
  sc.close();
 }
 
 private static boolean process(int nodeWithMaxDepth, int[] parent, int[] level, int[] query, int[] visited, int marker) {
  visitTillParent(nodeWithMaxDepth, parent, visited, marker);
  int maxDepth = 0;
  nodeWithMaxDepth = -1;
  for(int q : query) {
   if(visited[q] != marker && level[q] > maxDepth) {
    maxDepth = level[q];
    nodeWithMaxDepth = q;
   }
  }
 
  if(nodeWithMaxDepth == -1) return true;
 
  while(visited[nodeWithMaxDepth] != marker) {
   visited[nodeWithMaxDepth] = marker;
   nodeWithMaxDepth = parent[nodeWithMaxDepth];
  }
 
  for(int q : query) {
   if(visited[q] != marker || level[q] < level[nodeWithMaxDepth]) return false;
  }
  return true;
 }
 
 private static void visitTillParent(int nodeWithMaxDepth, int[] parent, int[] visited, int marker) {
  visited[nodeWithMaxDepth] = marker;
  while(parent[nodeWithMaxDepth] != -1) {
   nodeWithMaxDepth = parent[nodeWithMaxDepth];
   visited[nodeWithMaxDepth] = marker;
  }
 }
 
 private static void preProcess(Map<Integer, Set<Integer>> tree, int[] level, int[] parent) {
  boolean[] visited = new boolean[level.length];
  Queue<Integer> bfsQueue = new LinkedList<>();
 
        int u = 1;
  parent[u] = -1;
  level[u] = 0;
  bfsQueue.add(u);
  visited[u] = true;
 
  while(!bfsQueue.isEmpty()) {
   int n = bfsQueue.size();
   while(n-- > 0) {
    int parentNode = bfsQueue.poll();
    Set<Integer> children = tree.get(parentNode);
    for(Integer child : children) {
     if(!visited[child]) {
      parent[child] = parentNode;
      level[child] = level[parentNode]+1;
      visited[child] = true;
      bfsQueue.add(child);
     }
    }
   }
  }
 }
 
 private static void addPath(Map<Integer, Set<Integer>> tree, Integer u, Integer v) {
  addEdge(tree, u, v);
  addEdge(tree, v, u);
 }
 
 private static void addEdge(Map<Integer, Set<Integer>> tree, Integer u, Integer v) {
  if(!tree.containsKey(u)) tree.put(u, new HashSet<>());
  tree.get(u).add(v);
 }
}

July Long Challenge 2021 Solutions

• Maximum Production
• Relativity
• XxOoRr
• Optimal Denomination
• K Path Query
• Chef vs Bharat
• Chef and Pairs
• Even Odd Partition
• Dakimakura Distribition
• Madoka and Ladder Decomposition

Weekly Contest 247

• Maximum Product Difference Between Two Pairs
• Cyclically Rotating a Grid
• Number of Wonderful Substrings
• Count Ways to Build Rooms in an Ant Colony

Biweekly Contest 55

• Remove One Element to Make the Array Strictly Increasing
• Remove All Occurrences of a Substring
• Maximum Alternating Subsequence Sum
• Design Movie Rental System