 # COW3D-Editorial

Author: Himanshu Manwani
Tester: Himanshu Manwani
Editorialist: Kushagra Kinger

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
{
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;
{
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;
}
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;
}
``````

Problem Code: https://www.codechef.com/problems/COW3D

This problem taught me several things Thanks ! it was a nice contest

1 Like

please provide editorial for G problem also

You are welcome.
There were other approaches of solving this problem involving logn dynamics which involved computation of lca through binary lifting or sparse matrix precomputation , but in this problem as you see the solution is all linear. The relation between arrival departure times and ancestor child relation is a very important concept.

My code using binary lifting fails. Can you provide some test case/ logic error in my code, causing WA ?

Code seems fine, I also submitted a code with similar approach and it worked. U can try using 19 instead of 31, it makes no difference , but checking beyond 19 is not necessary,so just try

I optimized here going from depth[node1] to 0, still getting WA ? And BTW, why will it give WA if iterating from higher value ?

Upd: here is accepted solution. I iterated from `log(n)` down to `1`, but the question remains same. If in earlier case, I was trying to access invalid memory address (`log(n) < 31`) then it should have been `SIGSEGV` instead of WA. If not, for all i > log(n), `parent[node1][i] = parent[node2][i] = 0`. So, I still can’t figure out the reason for WA in above case. @ssjgz @everule1 @l_returns Can you help ?

@kkdrummer also, is there any issue with the testcases format ? (as I can’t see any python3/pypy solution getting accepted) example