MEX Tree
Contest: Codeforces Round 721 (Div. 2)
Difficulty rating: 2400
Tags: combinatorics, dfs and similar, implementation, math, trees

You are given a tree with $$$n$$$ nodes, numerated from $$$0$$$ to $$$n-1$$$. For each $$$k$$$ between $$$0$$$ and $$$n$$$, inclusive, you have to count the number of unordered pairs $$$(u,v)$$$, $$$u \neq v$$$, such that the MEX of all the node labels in the shortest path from $$$u$$$ to $$$v$$$ (including end points) is $$$k$$$.

The MEX of a sequence of integers is the smallest non-negative integer that does not belong to the sequence.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^{5}$$$).

The next $$$n-1$$$ lines of each test case describe the tree that has to be constructed. These lines contain two integers $$$u$$$ and $$$v$$$ ($$$0 \le u,v \le n-1$$$) denoting an edge between $$$u$$$ and $$$v$$$ ($$$u \neq v$$$).

It is guaranteed that the given edges form a tree.

It is also guaranteed that the sum of $$$n$$$ for all test cases does not exceed $$$2 \cdot 10^{5}$$$.

Output format:
For each test case, print $$$n+1$$$ integers: the number of paths in the tree, such that the MEX of all the node labels in that path is $$$k$$$ for each $$$k$$$ from $$$0$$$ to $$$n$$$.

Constraints:
Time limit: 1.5 s
Memory limit: 256.0 MB

Note:
1. In example case $$$1$$$,    For $$$k = 0$$$, there is $$$1$$$ path that is from $$$2$$$ to $$$3$$$ as $$$MEX([2, 3]) = 0$$$.  For $$$k = 1$$$, there are $$$2$$$ paths that is from $$$0$$$ to $$$2$$$ as $$$MEX([0, 2]) = 1$$$ and $$$0$$$ to $$$3$$$ as $$$MEX([0, 2, 3]) = 1$$$.  For $$$k = 2$$$, there is $$$1$$$ path that is from $$$0$$$ to $$$1$$$ as $$$MEX([0, 1]) = 2$$$.  For $$$k = 3$$$, there is $$$1$$$ path that is from $$$1$$$ to $$$2$$$ as $$$MEX([1, 0, 2]) = 3$$$  For $$$k = 4$$$, there is $$$1$$$ path that is from $$$1$$$ to $$$3$$$ as $$$MEX([1, 0, 2, 3]) = 4$$$.
2. In example case $$$2$$$,    For $$$k = 0$$$, there are no such paths.  For $$$k = 1$$$, there are no such paths.  For $$$k = 2$$$, there is $$$1$$$ path that is from $$$0$$$ to $$$1$$$ as $$$MEX([0, 1]) = 2$$$.

Example input:
2
4
0 1
0 2
2 3
2
1 0

Example output:
1 2 1 1 1 
0 0 1

Editorial:
This problem can be solved with two pointer approach. We will use the following simple formula to evaluate the number of paths with MEX = i,
$$$ans_i$$$ = (Number of paths with $$$MEX \ge i$$$) - (Number of paths with $$$MEX > i$$$).
First we root the tree at node $$$0$$$ and calculate the subtree sizes using a basic subtree DP. Now we can easily calculate answer for $$$0$$$ by just summing up the $$$size \cdot (size-1)/2$$$ of its children. Since total number of paths are $$$\left(\begin{array}{c}n\\ 2\end{array}\right)$$$, the number of paths with $$$MEX > 0$$$ are $$$\left(\begin{array}{c}n\\ 2\end{array}\right) - ans_0$$$ and we will maintain these paths which are having $$$MEX > i$$$ for every $$$i$$$ in a variable lets say $$$P$$$. Now the main idea is that for the $$$MEX$$$ of a path to be equal to $$$i$$$ it must contain all nodes from $$$0...i-1$$$ and not $$$i$$$. It can be seen that if we have current $$$MEX = i$$$ in some path then this path can only be extended from both ends as for $$$MEX > i$$$ this whole path must be included. So we start with our $$$2$$$ pointers initially $$$l = 0,r = 0$$$ i.e. both at the root. We will also be maintaining a visited array which will be denoting all those vertices which are lying in our path from $$$l$$$ to $$$r$$$. Now we loop from $$$1$$$ to $$$n$$$ and successively calculate their answers. Suppose we need to add some vertex $$$i$$$ to the path, then if the current vertex is already in the path i.e. already visited then we can just continue as the variable $$$P$$$ will remain same. In the other case, a possible approach is to just recursively move to the parent marking them as visited until we find a previously visited node. Let that node be $$$U$$$. Note that we will always break at the root as it is marked visited in the initial step.
Now the following two cases arise,
• The node $$$U$$$ is one of the endpoints $$$l$$$ or $$$r$$$. In this case we can simply calculate the number of paths having $$$MEX = i$$$. See the diagram below, we are having $$$P$$$ from previous calculations the number of paths having $$$MEX \ge i$$$ and the number of paths with $$$MEX > i$$$ (actually those paths which include all nodes from $$$0$$$ to $$$i-1$$$) can simply be seen as $$$subtree_i \cdot subtree_l$$$ or $$$subtree_i \cdot subtree_r$$$ depending on which two endpoints are there now. It should be noted that we also need to update the subtree sizes as we move up to parent recursively, by subtracting the $$$subtree_v$$$ from $$$subtree_{parent(v)}$$$. After updating the $$$l$$$ and $$$r$$$ pointers, the answer for $$$MEX = i$$$ is simply $$$P - subtree_l \cdot subtree_r$$$ and finally we update the variable $$$P = subtree_l \cdot subtree_r$$$ denoting for $$$i + 1$$$, the number of paths with $$$MEX \ge i+1$$$.
• The next case is when $$$U$$$ is not among the endpoints $$$l$$$ and $$$r$$$, then in this case $$$ans_i = P$$$ and all other remaining i.e $$$MEX \ge i+1$$$ are zero, since we can never find a path which can contain all vertices from $$$0$$$ to $$$i$$$.