In-Out Time, Ancestor, Subtree Size Calculations

Previously we learned about Ancestor, Subtree, and some basic stuff.  Today we will learn some more basic things like,

1. What is In-Time, Out-Time, and why do we need to calculate this?
2. How to check A vertices 'u' is an Ancestor of vertices 'v' or not? 

3. Calculate the size of a subtree ( including this node).

So let's start,

Look at the picture, here we tried to calculate in and out time. Basically in and out  time of a tree can be calculated in visiting order. We see, given order is [1,2,4,8,5,3,6,9,7], it means after considering root '1', we started visiting(DFS) in this order. First, assume that visiting moment is time(in Second). Let's take a node '2', we marked it with [2,9], which means when we entered in this node the time was 2 and after visiting some depth children when again we come back to node '2', the time was 9 (in second).

I guess the In-Out time concept is clear now.

Let's move to Ancestor. Suppose we have given two nodes 'u' and 'v', we have to find out in the given tree 'u' is the Ancestor of 'v' or not.

From the definition of Ancestor we know, consider a node 'u' and from 'u' if we start visit towards the root node, that's all nodes found, they are all ancestors of node 'u'. For example, 6, 3, 1 they are all Ancestor of 7.

This can be easily checked by traversing(using dfs), but time complexity will be huge if we have given Q queries.

So, conditions are simple for checking ancestor using in-out time, just think why it works?

Ancestor: In time of 'u'  > In time of 'v' and Out time 'u' < Out time of 'u';

Similarly, we can calculate Subtree size. Here again, we can solve it using in-out time. 

So, the condition for subtree is,

Subtree: (Out time of 'u' - In time of 'v' + 1)/2;

Again think yourself, why it works? But we can also calculate subtree size by using a simple DFS, try it.

For better understanding see the code.

Related Problems:
Subordinates-cses