PROBLEM LINK:
Author: Himanshu Manwani
Tester: Himanshu Manwani
Editorialist: Kushagra Kinger
DIFFICULTY:
EASY
PREREQUISITES:
Depth-First-Search
PROBLEM:
You are given a rooted tree. Now in each query u are given a set of vertices and u have to determine whether there is a vertex which lies on the simple path from the root to each vertex in the set.
QUICK EXPLANATION:
Formally we have to find the Common Ancestor of all the vertices in the set.Obtain the arrival and departure time of each node in dfs starting from root . Now the vertex which corresponds to the minimum arrival time and maximum departure time is the answer. If these vertices are not same, then answer does not exist.
EXPLANATION:
We have a list of k-nodes in a sub-tree rooted at 1 for every query.
All we need to do is find the node which lies in the simple path from the root to the other k-1 nodes.
In other words,we are asked to find the node which is the ancestor of the remaining k-1 vertices.
Here’s an easy lemma for you:
For two nodes u and v,if u is the ancestor of v, then the start time and finish time for u and v follow this rule:
ST[u]<ST[v] and FT[u]>FT[v]
where ST and FT represent start time and finish time respectively.
(arrival and departure time ).
We can do this using the following code:
A simple DFS traversal of the tree would give us the start and finish times for each node.
void dfs(int v, int par = -1) {
ST[v] = T++;
for (auto to : g[v]) {
if (to == par) continue;
dfs(to, v);
}
FT[v] = T++;
}
It’s quite simple when you come to think of it.
Now we just need to extend this to a set of k vertices.
Now the Godfather Node is simply the node which arrives the earliest and departs last.
For every query we look for a node in the given set, which has the earliest start time and highest departure time.
However there’s a catch,if the minimum arrival time and maximum departure time do not belong to the same node, print -1.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MOD 1000000007
const int MAX_ = 200005;
struct graph
{
vector<int> adj; // connections
int ar , dp; //arrival and departure time.
};
graph G[MAX_]; // 1 indexing graph
void dfs(int start,int par = -1)
{
static int time = 0;
G[start].ar = ++time;
for(int i =0;i<G[start].adj.size();i++)
{
int v = G[start].adj[i];
if(v != par)
{
dfs(v,start);
}
}
G[start].dp = ++time;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,q; cin>>n>>q; //n- number of nodes , q -queries
for(int i =0;i<n-1;i++) // (n-1 edges)
{
int x,y; cin>>x>>y;
G[x].adj.push_back(y);
G[y].adj.push_back(x);
}
dfs(1);
while(q--)
{
int k; cin>>k;
vector<int> ele(k); /// query elements
for(int i =0;i<k;i++)
{
cin>>ele[i];
}
int id1 = -1,id2 = -1;
int min_arrival_time = INT_MAX;
int max_departure_time = -1;
for(int i =0;i<k;i++)
{
int node = ele[i];
int arr_time = G[node].ar; // arrival and departure times of query
node.
int dep_time = G[node].dp;
if(arr_time < min_arrival_time)
{
min_arrival_time = arr_time ;
id1 = node;
}
if(dep_time > max_departure_time)
{
max_departure_time = dep_time;
id2 = node;
}
}
if(id1 == id2)cout << id1 << "\n";
else cout << "-1\n";
}
return 0;
}
