### PROBLEM LINKS

### DIFFICULTY

Medium

### PREREQUISITES

Depth First Search

### PROBLEM

What is the lexicographically K^{th} path out of the N^{2} paths in a tree.

### EXPLANATION

The most cumbersome part of the problem is actually building the graph to run the DFS on. Once that is ready, we will see that the answer can be found quite comfortably.

The input format gives you N-1 edges in the form of (u, v) pairs. The limit on N is large, hence a static array to store the adjacency list is out of question. You can create lists of numbers to store connected vertices for each vertex, but there is an important constraint that must be taken care of.

We wish to find the lexicographically K^{th} path. This means that for a vertex, you wish to know the connected vertices in increasing order of labels.

There is a clever way to achieve this.

- For each pair of vertices (u, v) for an edge, ensure that u < v
- Sort the edges in increasing order. First by u, then by v

Now, if you will maintain a queue of vertices for each vertex in the adjacency list, you should process the list of edges in increasing order. If you maintain a stack of vertices for each vertex in the adjacency list, process the list of edges in reverse order.

Once the graph is built, we move on to find the lexicographically K^{th} path. The first insight that helps is

**There are N paths that start from each vertex**

Thus, the vertex from which the K^{th} path starts is

U = ceil( (K-1) / N )

We wish to find the

k = (K - (U - 1)*N)^{th}

path that starts from the U^{th} cell.

First, we root the tree at U. We assume that the reverse edges of the undirected tree are deleted. Now, we find the number of vertices in the subtree rooted at each vertex.

size[] = 0 function build_size( u ) { size[u] = 1 for v connected to u size[u] = size[u] + 1 build_size( v, u ) } build_size( U , 0 )

The reason we build size is because now we know how many paths are possible starting from each vertex. This information helps us ignore the required number of paths when building the k^{th} path.

function print_it( u, k ) print u k = k - 1 if k == 0 return for v connected to u if size[v] ≥ k print_it( v, k ) return k = k - size[v] print_it( U, k )

### SETTER’S SOLUTION

Can be found here

### TESTER’S SOLUTION

Can be found here