# K Path Query Codechef Solution

Page Contents

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

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

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 ;
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 = u;
t = 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[i] = k;
t[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[i]+" "+t[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];

int u = 1;
parent[u] = -1;
level[u] = 0;
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;
}
}
}
}
}

private static void addPath(Map<Integer, Set<Integer>> tree, Integer u, Integer v) {
}

private static void addEdge(Map<Integer, Set<Integer>> tree, Integer u, Integer v) {
if(!tree.containsKey(u)) tree.put(u, new HashSet<>());
}
}``````

## Biweekly Contest 55

### 2 thoughts on “K Path Query Codechef Solution”

1. In k path query n is not initalized in 1st program.java once check it!!!!!

• 