K Path Query | CodeChef Solution

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

Task

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 v₁, v₂, . . . ,v_K. 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 K_i — the number of vertices in the current query. Then K_i integers follow: v₁, v₂ , . . . ,v_Ki.

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 ≤ 10⁵
• 1 ≤ u, v, v_j ≤ N
• 1 ≤ Q ≤ 10⁵
• 1 ≤ K_i ≤ 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 ⋅ 10⁵.
• For each test case, the sum of K_i over all queries does not exceed 10⁵.

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 − 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
input = sys.stdin.readline

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())
        adj[u].append(v)
        adj[v].append(u)

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

    while q:
        parentNode = q.popleft()
        for child in adj[parentNode]:
            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];
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);
}
}

Disclaimer: The above Problem (K Path Query) is generated by CodeChef but the Solution is Provided by Codingbroz. This tutorial is only for Educational and Learning Purpose.