KTHPATH - Editorial

editorial
, , , , ,
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

Medium

PREREQUISITES

Depth First Search

PROBLEM

What is the lexicographically Kth path out of the N2 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 Kth 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 Kth path. The first insight that helps is

There are N paths that start from each vertex

Thus, the vertex from which the Kth path starts is

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

We wish to find the

k = (K - (U - 1)*N)th

path that starts from the Uth 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 kth 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

1 Like
2

Aren’t there N*(N+1)/2 paths in a tree?

3

It is explained in the problem statement that:
“Generally, there are N*N paths. Note that we are counting paths from each node onto itself as well.”

We are counting paths from each node to itself. And, the direction of the path matters. That is, the path (A -> B) is different from the path (B -> A), for this problem.
Therefore, the number of paths is N*N.