COW3D-Editorial

PROBLEM LINK:

Practice
Contest

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

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