Compruebe si dos Nodes están en la misma ruta en un árbol

Dado un árbol (no necesariamente un árbol binario) y un número de consultas tales que cada consulta toma dos Nodes del árbol como parámetros. Para cada par de consultas, encuentre si dos Nodes están en la misma ruta desde la raíz hasta el final.

Por ejemplo, considere el siguiente árbol, si las consultas dadas son (1, 5), (1, 6) y (2, 6), entonces las respuestas deben ser verdaderas, verdaderas y falsas respectivamente. 

// C++ program to check if given pairs lie on same
// path or not.
#include<bits/stdc++.h>
using namespace std;
const int MAX = 100001;
 
// To keep track of visited vertices in DFS
bool visit[MAX] = {0};
 
// To store start and end time of all vertices
// during DFS.
int intime[MAX];
int outtime[MAX];
 
// initially timer is zero
int timer = 0;
 
// Does DFS of given graph and fills arrays
// intime[] and outtime[]. These arrays are used
// to answer given queries.
void dfs(vector<int> graph[], int v)
{
    visit[v] = true;
 
    // Increment the timer as you enter
    // the recursion for v
    ++timer;
 
    // Upgrade the in time for the vertex
    intime[v] = timer;
 
    vector<int>::iterator it = graph[v].begin();
    while (it != graph[v].end())
    {
        if (visit[*it]==false)
            dfs(graph, *it);
        it++;
    }
 
    // increment the timer as you exit the
    // recursion for v
    ++timer;
 
    // upgrade the outtime for that node
    outtime[v] = timer;
}
 
// Returns true if 'u' and 'v' lie on same root to leaf path
// else false.
bool query(int u, int v)
{
    return ( (intime[u]<intime[v] && outtime[u]>outtime[v]) ||
             (intime[v]<intime[u] && outtime[v]>outtime[u]) );
}
 
// Driver code
int main()
{
    // Let us create above shown tree
    int n = 9; // total number of nodes
    vector<int> graph[n+1];
    graph[1].push_back(2);
    graph[1].push_back(3);
    graph[3].push_back(6);
    graph[2].push_back(4);
    graph[2].push_back(5);
    graph[5].push_back(7);
    graph[5].push_back(8);
    graph[5].push_back(9);
 
    // Start dfs (here root node is 1)
    dfs(graph, 1);
 
    // below are calls for few pairs of nodes
    query(1, 5)? cout << "Yes\n" : cout << "No\n";
    query(2, 9)? cout << "Yes\n" : cout << "No\n";
    query(2, 6)? cout << "Yes\n" : cout << "No\n";
 
    return 0;
}

// Java program to check if given
// pairs lie on same path or not.
import java.util.*;
 
class GFG{
     
static int MAX = 100001;
 
// To keep track of visited vertices in DFS
static boolean []visit = new boolean[MAX];
 
// To store start and end time of all vertices
// during DFS.
static int []intime = new int[MAX];
static int []outtime = new int[MAX];
 
// Initially timer is zero
static int timer = 0;
 
// Does DFS of given graph and fills arrays
// intime[] and outtime[]. These arrays are used
// to answer given queries.
static void dfs(Vector<Integer> graph[], int v)
{
    visit[v] = true;
 
    // Increment the timer as you enter
    // the recursion for v
    ++timer;
 
    // Upgrade the in time for the vertex
    intime[v] = timer;
 
    for(int it : graph[v])
    {
        if (visit[it] == false)
            dfs(graph, it);
             
        it++;
    }
 
    // Increment the timer as you exit the
    // recursion for v
    ++timer;
 
    // Upgrade the outtime for that node
    outtime[v] = timer;
}
 
// Returns true if 'u' and 'v' lie on
// same root to leaf path else false.
static boolean query(int u, int v)
{
    return ((intime[u] < intime[v] &&
            outtime[u] > outtime[v]) ||
            (intime[v] < intime[u] &&
            outtime[v] > outtime[u]));
}
 
// Driver code
public static void main(String[] args)
{
     
    // Let us create above shown tree
    int n = 9; // total number of nodes
     
    @SuppressWarnings("unchecked")
    Vector<Integer> []graph = new Vector[n + 1];
    for(int i = 0; i < graph.length; i++)
        graph[i] = new Vector<Integer>();
         
    graph[1].add(2);
    graph[1].add(3);
    graph[3].add(6);
    graph[2].add(4);
    graph[2].add(5);
    graph[5].add(7);
    graph[5].add(8);
    graph[5].add(9);
 
    // Start dfs (here root node is 1)
    dfs(graph, 1);
 
    // Below are calls for few pairs of nodes
    if (query(1, 5))
        System.out.print("Yes\n" );
    else
        System.out.print("No\n");
         
    if (query(2, 9))
        System.out.print("Yes\n");
    else
        System.out.print("No\n");
     
    if (query(2, 6))
        System.out.print("Yes\n" );
    else
        System.out.print("No\n");
}
}
 
// This code is contributed by Princi Singh

# contributed by saurabh_jain861
# Python3 program to check if given
# pairs lie on same path or not.
 
# Does DFS of given graph and fills
# arrays intime[] and outtime[].
# These arrays are used to answer
# given queries.
def dfs(graph, v):
    global intime, outtime, visit, MAX, timer
    visit.add(v)
 
    # Increment the timer as you enter
    # the recursion for v
    timer += 1
 
    # Upgrade the in time for the vertex
    intime[v] = timer
    it = 0
    while it < len(graph[v]):
        if (graph[v][it] not in visit):
            dfs(graph, graph[v][it])
        it += 1
 
    # increment the timer as you
    # exit the recursion for v
    timer += 1
 
    # upgrade the outtime for that node
    outtime[v] = timer
 
# Returns true if 'u' and 'v' lie on
# same root to leaf path else false.
def query(u, v):
    global intime, outtime, visit, MAX, timer
    return ((intime[u] < intime[v] and
             outtime[u] > outtime[v]) or
            (intime[v] < intime[u] and
             outtime[v] > outtime[u]) )
 
# Driver code
MAX = 100001
 
# To keep track of visited vertices in DFS
visit =set()
 
# To store start and end time of
# all vertices during DFS.
intime = [0] * MAX
outtime = [0] * MAX
 
# initially timer is zero
timer = 0
 
# Let us create above shown tree
n = 9 # total number of nodes
graph = [[] for i in range(n+1)]
graph[1].append(2)
graph[1].append(3)
graph[3].append(6)
graph[2].append(4)
graph[2].append(5)
graph[5].append(7)
graph[5].append(8)
graph[5].append(9)
 
# Start dfs (here root node is 1)
dfs(graph, 1)
 
# below are calls for few pairs of nodes
print("Yes") if query(1, 5) else print("No")
print("Yes") if query(2, 9) else print("No")
print("Yes") if query(2, 6) else print("No")
 
# This code is contributed by PranchalK

// C# program to check if given
// pairs lie on same path or not.
using System;
using System.Collections.Generic;
class GFG{
     
static int MAX = 100001;
 
// To keep track of visited
// vertices in DFS
static bool []visit =
       new bool[MAX];
 
// To store start and end
// time of all vertices
// during DFS.
static int []intime =
       new int[MAX];
static int []outtime =
       new int[MAX];
 
// Initially timer is zero
static int timer = 0;
 
// Does DFS of given graph
// and fills arrays intime[]
// and outtime[]. These arrays
// are used to answer given queries.
static void dfs(List<int> []graph,
                int v)
{
  visit[v] = true;
 
  // Increment the timer as
  // you enter the recursion
  // for v
  ++timer;
 
  // Upgrade the in time
  // for the vertex
  intime[v] = timer;
 
  foreach(int it in graph[v])
  {
    if (visit[it] == false)
      dfs(graph, it);
  }
 
  // Increment the timer as
  // you exit the recursion for v
  ++timer;
 
  // Upgrade the outtime for
  // that node
  outtime[v] = timer;
}
 
// Returns true if 'u' and
// 'v' lie on same root to
// leaf path else false.
static bool query(int u,
                  int v)
{
  return ((intime[u] < intime[v] &&
           outtime[u] > outtime[v]) ||
          (intime[v] < intime[u] &&
           outtime[v] > outtime[u]));
}
 
// Driver code
public static void Main(String[] args)
{   
  // Let us create above shown tree
  // total number of nodes
  int n = 9;
 
  List<int> []graph =
       new List<int>[n + 1];
   
  for(int i = 0;
          i < graph.Length; i++)
    graph[i] = new List<int>();
 
  graph[1].Add(2);
  graph[1].Add(3);
  graph[3].Add(6);
  graph[2].Add(4);
  graph[2].Add(5);
  graph[5].Add(7);
  graph[5].Add(8);
  graph[5].Add(9);
 
  // Start dfs (here root
  // node is 1)
  dfs(graph, 1);
 
  // Below are calls for few
  // pairs of nodes
  if (query(1, 5))
    Console.Write("Yes\n" );
  else
    Console.Write("No\n");
 
  if (query(2, 9))
    Console.Write("Yes\n");
  else
    Console.Write("No\n");
 
  if (query(2, 6))
    Console.Write("Yes\n" );
  else
    Console.Write("No\n");
}
}
 
// This code is contributed by Amit Katiyar