# K Path Query Solution | KPATHQRY | CODECHEF JULY CHALLENGE

View problem on codechef

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

``````Join telegram channel for updates

Java

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
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<>());
1. 