CTOUR - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice

Contest

Author: Abhineet Shrivastava, Ishank Bhardwaj

Tester: Ishank Bhardwaj

Editorialist: Abhineet Shrivastava

DIFFICULTY:

MEDIUM-HARD

PREREQUISITES:

Least Common Ancestor, DP, Graphs

PROBLEM:

Given a rooted tree with N nodes and Q queries. In each query, two
nodes A and B are given. The problem is to calculate path from node A to
node B using a special traversal. In the traversal from node A to node B,
you can reverse your direction only once. Reversing the direction means
earlier the you were going towards the root, then away from the root or
vice versa.

EXPLANATION:

The problem can be solved using LCA and dp on trees.

Pre-processing steps:

  1. Profit from root to all the nodes - profit[n].

  2. For calculating LCA in log(n).

  3. Using DP on trees, calculate the max profit for each node, if we are
    at the node and go towards the root and come back - up[n].

  4. Using DP on trees calculate the max profit for each node, if we are
    at the node and go towards downwards and come back - down[n].

Calculation steps:

Every query can be answered in O(log(n)).

There are three cases.

  1. If LCA (A, B)!= A or B. Then we have only one choice- going from A to LCA(A,B), then towards root to some extent and then to B. The total amount we can gain is profit[A] + profit[B] - 2 * profit[LCA(A, B)] + 2 * up[LCA(A, B)].

  2. If LCA(A, B) = A. Then we have two choices- going upwards from A and back, or going downwards from B and back. The total amount we can gain is profit[B] - profit[A] + 2 * max(up[A], down[B]).

  3. If LCA(A, B) = B. Then we have two choices- going upwards from B and back, or going downwards from A and back. The total amount we can gain is profit[A] - profit[B] + 2 * max(up[B], down[A]).

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.

1 Like