Hello.

I've just thought of a way to compute the linearization times (entry and exit) for a tree given by "the father of node $$$i$$$ is $$$p_i$$$ ($$$p_i \lt i$$$)" without the usual graph creation. This might improve the time of a submission (you no longer do push_backs) but I haven't tested. It is very niche (the number of problems where the tree is given in this way is small and those where you don't need the actual graph are even fewer) so feel free to ignore the blog. This might be well known to some people, but I never saw this so maybe someone can benefit from it. The following picture is a representation of what we are trying to achieve. We will also compute the subtree size for each node as it is required but if you cannot afford the extra memory you can probably reuse one of the arrays instead.

One can observe that the exit time is equal to the entry time + the subtree size. Also the entry times are increments of $$$1$$$ in the preorder traversal. The following code computes the arrays $$$in, out$$$ and $$$sz$$$.

for(i=0;i<N;++i)
    sz[i]=1;
for(i=N-1;i>0;--i)
    sz[p[i]]+=sz[i];

out[0]=1;
for(i=1;i<N;++i)
{
    in[i]=out[p[i]];
    out[p[i]]+=sz[i];
    out[i]=in[i]+1;
}

The first $$$2$$$ loops compute the $$$sz$$$ array, nothing special there. $$$in[i]=out[p[i]]$$$ has the effect of "starting" the preorder traversal at node $$$i$$$ from where $$$p[i]$$$ left. The increase of the exit time for the parent by $$$sz[i]$$$ has the effect of simulating the preorder traversal of node $$$i$$$ quickly, allowing the next son of $$$p[i]$$$ to start where $$$i$$$ left. To allow the sons of $$$i$$$ to do their traversal we set their start with $$$out[i]=in[i]+1$$$.

This trick seems simple enough to have been discovered at least $$$5$$$ times before.

As stated in the beggining, if storing $$$3$$$ arrays is too much memory (sorry for you) you can just replace $$$sz$$$ with $$$exit$$$. This is because you only need the size of a node when you process it.

Thanks for reading. Sorry if this appeared somewhere else before.