### PROBLEM LINK:

**Author:** Nick

**Tester:** Praveen Dhinwa

**Editorialist:** Ajay K. Verma

### DIFFICULTY:

Medium

### PREREQUISITES:

### PROBLEM:

We are given a directed tree, and a set of tickets, where each ticket has a cost associated with it, starts from a particular node, and can be used to traverse a given number of edges. The task is to answer several queries which ask about the smallest cost of reaching root from a given node in such a way that all edges are covered by a ticket, and a ticket is used only for edges forming a path.

### QUICK EXPLANATION:

Traverse all nodes of the tree in topological order (root to leaves), and compute the smallest cost for each node using the smallest costs for its ancestors. This will require computing the minimum cost among the nodes lying in a directed path from a node to its ancestor, which can be computed efficiently using skip list.

### EXPLANATION:

We are given a directed tree T (edges directed towards root). Each edge can be traversed in its direction and requires having a ticket. The tickets are bought from some of the nodes. Each ticket has a cost, an associated node from where it can be bought, and the number of edges on which it can be used. At any point one can carry exactly one ticket, this means a ticket can be used only on the edges which form a path from a node to one of its ancestors.

The task is to answer several queries which ask computing the smallest amount of the money that one needs to spend in order to reach root from a given node.

Suppose, we want to answer this question for node x. If there are no tickets available at node x, then of course we cannot reach root from x. On the other hand, let us assume that there are k tickets available with cost c_{1}, c_{2}, …, c_{k}, and reach d_{1}, d_{2}, …, d_{k}, then in order to reach root, we need to use one of these tickets. Based on this, we can actually compute the cost F(x) of the cheapest trip from x to root as follows:

F(x) = min_{1 <= i <= k} (c_{i} + min_{1 <= j <= di} F(y_{j}))

where y_{j} is the ancestor of x at a distance j.

Hence, the overall recurrence will look like this.

F(root) = 0

F(x) = inf, if x has no tickets available

F(x) = min_{1 <= i <= k} (c_{i} + min_{1 <= j <= di} F(y_{j}))

Since the computation of F(x) used the values F(y), where y is an ancestor of x, we should compute the values F() for nodes in the order from root to leaves, so that at any point needed values are already computed.

Using this approach, we can compute the value of F() for all nodes in O (NM) time, as for each ticket, we need to look at the values of the ancestors up to distance min(d, h), where d is the reach of the ticket and h is the distance from the root to the origin of this ticket, which is bounded by N. Hence, we need to check at most O (NM) previously computed values. This approach will certainly not work on the large test cases.

If we could somehow the speedup of the computation of

min_{1 <= j <= di} F(yj)

then, the runtime can be reduced significantly, and next we discuss how to do this using the skip list.

We want to associate a value F(x) with each node, so that the minimum of the all F() values along a path from a node to one of its ancestors can be computed fast.

For this purpose, we store a list G[1…lg N] of O (lg N) values at each node, the i-th of these values is the minimum F() value among all nodes which are ancestor of this node, and at a distance < 2^{i} from this node. We also need to store the ancestor which is at 2^{i} distance from this node. These ancestors are stored in another list H[1…lg N] for this node.

Using these values one can easily compute the minimum of F() values on the path from a node x to its ancestor at distance d. Supposed that

d = 2^{t1} + 2^{t2} + … + 2^{tr}

We first look at the t1-th element in the list of the current node, which gives us the minimum of all node values which are at most distance 2^{t1} from this node. We also get the ancestor at 2^{t1} distance, which will become our new current node, and then we look for the t2-th element of the list of this new current node, and so on. This way, we compute the minimum of all 2^{t1} + 2^{t2} + … + 2^{tr} = d values. Since there can be at most lg N terms in the binary representation of a number smaller than N, the value of r must not exceed lg N. Hence, we can compute the minimum of all d values in O (lg N) time.

Next, let us see how to compute the lists G and H for a node x.

G_{x}[0] = F(x), as there is a single node to consider

H_{x}[0] = parent(x)

In order to compute G_{x}[i] and H_{x}[i], for larger values of i, we use the following observation:

Since 2^{i} = 2^{i - 1} + 2^{i - 1
}

We first look the at the first 2^{i - 1} ancestors of x. The minimum of F() values of these ancestors is G_{x}[i - 1]. and the ancestor at 2^{i - 1} distance is H_{x}[i - 1]. From this ancestor, we can get the minimum of next 2^{i - 1} values, which is given by G_{H[i - 1]}[i - 1]. Hence,

G_{x}[i] = min(G_{x}[i - 1], G_{H[i - 1]}[i - 1])

H_{x}[i] = H_{H[i - 1]}[i - 1]

This means the skip list for a single node can be computed in O (lg N) using the skip lists of its ancestors.

Hence, we have reduced the computation of

min_{1 <= j <= di} F(yj)

to O (lg N) time.

This means the F() values of all nodes can be computed in O ((M + N) lg N) time,

which will run in time.

### TIME COMPLEXITY:

O (Q + (M + N) lg N)

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution will be put up soon.

Tester’s solution will be put up soon.