# K Path Query | CodeChef Solution

Hello coders, today we are going to solve K Path Query CodeChef Solution whose Problem Code is KPATHQRY.

You’re given a tree with N vertices numbered from 1 to N. Your goal is to handle Q queries. For each query you are given K nodes v1, 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 T – the number of test cases. The description of T test cases follows.
• The first line of each test case contains a single integer N.
• Each of the following N âˆ’ 1 lines contains two integers u and v denoting an edge between nodes u and v.
• The next line contains a single integer Q – the number of queries.
• The next Q lines describe queries. The i-th line describes the i-th query and starts with the integer Ki â€” the number of vertices in the current query. Then Ki integers follow: v1, 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 â‰¤ 10
• 1 â‰¤ N â‰¤ 105
• 1 â‰¤ u, v, vj â‰¤ N
• 1 â‰¤ Q â‰¤ 105
• 1 â‰¤ Ki â‰¤ N for each valid i.
• The edges form a valid tree.
• All vertices in a single query are distinct.
• the sum of N over all test cases does not exceed 2 â‹… 105.
• For each test case, the sum of Ki over all queries does not exceed 105.

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 âˆ’ 6.
• For the second query there is no simple path that covers all the given vertices.

## Solution – K Path Query

### C++

```#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
using namespace std;
void visitill_parent(int N_w_max_depth, vector<int> &parent, vector<int> &visited, int marker)
{
visited[N_w_max_depth] = marker;

while (parent[N_w_max_depth] != -1)
{
N_w_max_depth = parent[N_w_max_depth];
visited[N_w_max_depth] = marker;
}
}

int process(int N_w_max_depth, vector<int> &parent, vector<int> &level, vector<int> &query, vector<int> &visited, int marker)
{
visitill_parent(N_w_max_depth, parent, visited, marker);
int max_depth = 0;
N_w_max_depth = -1;

for (auto q : query)
{
if (visited[q] != marker && level[q] > max_depth)
{
max_depth = level[q];
N_w_max_depth = q;
}
}

if (N_w_max_depth == -1)
return 1;
while (visited[N_w_max_depth] != marker)
{
visited[N_w_max_depth] = marker;
N_w_max_depth = parent[N_w_max_depth];
}

for (auto q : query)
{

if (visited[q] != marker || level[q] < level[N_w_max_depth])
{
return 0;
}
}
return 1;
}
void bfs(map<int, set<int>> &tree, vector<int> &lev, vector<int> &par)
{

vector<int> visited(lev.size(), 0);

queue<int> qu;
int u = 1;
par[u] = -1;
lev[u] = 0;
qu.push(1);
visited[u] = 1;
while (!qu.empty())
{
int n = qu.size();
while (n--)
{
int parentnode = qu.front();
qu.pop();
set<int> children = tree[parentnode];
for (auto child : children)
{
if (!visited[child])
{
par[child] = parentnode;
lev[child] = lev[parentnode] + 1;
visited[child] = 1;
qu.push(child);
}
}
}
}
}
int main()
{
int T;
cin >> T;
while (T--)
{
int n;
cin >> n;
map<int, set<int>> mp;
for (int i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
mp[u].insert(v);
mp[v].insert(u);
}

//to maintain level
vector<int> lev(n + 1);
//to maintain parent of the nodes
vector<int> par(n + 1);

bfs(mp, lev, par);
vector<int> visited(n + 1, 0);
int Q;
cin >> Q;
for (int i = 1; i <= Q; i++)
{
int K;
cin >> K;
vector<int> query(K);

int max_depth = 0;
int N_W_max_depth = -1;
for (int j = 0; j < K; j++)
{
cin >> query[j];
if (lev[query[j]] > max_depth)
{
max_depth = lev[query[j]];
N_W_max_depth = query[j]; //to find the deepest node in qury
}
}
int ans = process(N_W_max_depth, par, lev, query, visited, i);
if (ans == 1)
cout << "YES\n";
else
cout << "NO\n";
}
}
return 0;
}```

### Python

```import sys
from collections import deque

for _ in range(int(input())):
n = int(input())
adj = [[] for _ in range(n+1)]
for _ in range(n-1):
u, v = map(int, input().split())

parent = [-1]*(n+1)
level = [0]*(n+1)
vis = [0]*(n+1)
vis[1] = 1
q = deque([1])

while q:
parentNode = q.popleft()
if not vis[child]:
vis[child] = 1
q.append(child)
level[child] = 1+level[parentNode]
parent[child] = parentNode

vis = [-1]*(n+1)
for mark in range(int(input())):
k, *queries = map(int, input().split())
# finding deepest node
maxDepth = 0
nodeWithMaxDepth = 1
for query in queries:
if level[query] > maxDepth:
maxDepth = level[query]
nodeWithMaxDepth = query

# marking all nodes between nodeWithMaxDepth and root inclusive
vis[nodeWithMaxDepth] = mark
while parent[nodeWithMaxDepth] != -1:
nodeWithMaxDepth = parent[nodeWithMaxDepth]
vis[nodeWithMaxDepth] = mark

# finding second deepest node
maxDepth = 0
nodeWithMaxDepth = 1
for query in queries:
if vis[query] != mark and level[query] > maxDepth:
maxDepth = level[query]
nodeWithMaxDepth = query

# if given nodes are already visited
if nodeWithMaxDepth == 1:
print('YES')
continue

# find the point of intersection between both the paths
# from first deepest node to root and from second deepest node to root
while vis[nodeWithMaxDepth] != mark:
vis[nodeWithMaxDepth] = mark
nodeWithMaxDepth = parent[nodeWithMaxDepth]

# check whether any node is unvisited or present above the intersection point
# if any of the condition is true then there is no simple path that covers the given nodes
for query in queries:
if vis[query] != mark or level[query] < level[nodeWithMaxDepth]:
print('NO')
break
else:
print('YES')

```

### Java

```/* package codechef; // don't place package name! */

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