You are not logged in. Please login at www.codechef.com to post your questions!

×

CTOUR - Editorial

PROBLEM LINK:

Practice

Contest

Author: Abhineet ShrivastavaIshank 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

This question is marked "community wiki".

asked 27 Oct '18, 23:35

abhineet14's gravatar image

5★abhineet14
4318
accept rate: 16%

edited 27 Oct '18, 23:40

vijju123's gravatar image

4★vijju123 ♦♦
15.2k11860

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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