## Tubby and Tom – DE Shaw OA

From now onwards, Tubby = D and Tom = C. So D has to catch C and the first turn is of D. So, the very first thing is to create a tree from the given edge list. Here we create an adjacency list.

```int min_time(int G_nodes, vector<int> G_from, vector<int> G_to
, int D, int C){

for(int i=0;i<G_nodes-1;i++){
//Edges are undirected
}
}
```

Now, we will apply DFS and create distance_d and distance_c arrays which denotes the distance of ith node from initial position of D and C respectively. This means, now we know the time D and C will take to reach any particular node from it’s starting position.

```void dfs(int node, int p, int depth, vector<int> adj[], int dist[]){
dist[node] = depth;
if (i == p) continue;
}
}

int min_time(int G_nodes, vector<int> G_from, vector<int> G_to
, int D, int C){

for(int i=0;i<G_nodes-1;i++){
//Edges are undirected
}

int distance_d[G_nodes+1], distance_c[G_nodes+1];

}
```

If at a node, D reaches first, i.e., distance_d[node] <= distance_c[node]+1, than C will never go to such node (not optimal). Thus, when distance_d[node] > distance_c[node]+1, C can be pruned and the ans will be updated as ans = max(ans, distance_d[node] + distance_d[node] -1). Because when C is caught, it has made one step less than what D has made.

Note : Answer always exist, as tree does not contain cycles. For detail explanation, I will include a link to my youtube video below!

Complete Code :

```void dfs(int node, int p, int depth, vector<int> adj[], int dist[]){
dist[node] = depth;
if (i == p) continue;
}
}

int min_time(int G_nodes, vector<int> G_from, vector<int> G_to
, int D, int C){

for(int i=0;i<G_nodes-1;i++){
//Edges are undirected
}

int distance_d[G_nodes+1], distance_c[G_nodes+1];