×

# CTOUR - Editorial

Practice

Contest

Tester: Ishank Bhardwaj

Editorialist: Abhineet Shrivastava

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

This question is marked "community wiki".

4318
accept rate: 16%

15.2k11860

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,498
×1,237
×242
×50
×14

question asked: 27 Oct '18, 23:35

question was seen: 126 times

last updated: 27 Oct '18, 23:40