PROBLEM LINK:
Author: Abhineet Shrivastava, Ishank Bhardwaj
Tester: Ishank Bhardwaj
Editorialist: Abhineet Shrivastava
DIFFICULTY:
MEDIUMHARD
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.
Preprocessing steps:

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

For calculating LCA in log(n).

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]. 
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.

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**  2 * profit[LCA(A, B)] + 2 * up[LCA(A, B)].

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**  profit[A] + 2 * max(up[A], down**).

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** + 2 * max(up**, down[A]).
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.