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






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.


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.


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.


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)
    G[start].dp = ++time;

int main()
    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;
        int k;    cin>>k;
        vector<int> ele(k);    /// query elements
        for(int i =0;i<k;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 
            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;
1 Like

Problem Code: COW3D Problem - CodeChef

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. :frowning_face:
@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