you have been given tree, find a shortest path to travel from 1 to N, such that you visits some given set of nodes in your path from 1 to N. you are allowed to visit same node multiple times.
eg — N = 5
1
/ \
2 3
/ \
4 5
node_to_visit_in_path = { 2 ,4 }
solution — 6 ( 1 -> 2 -> 1 -> 3 -> 4 -> 3 -> 5)
CONSTRAINTS;
N UPTO ( 2 * 1e5 )
size of {node_to_visit_in_path} : upto N-1
is this a famous kind of problem ?, i think similar problem i have see somewhere.
Can u specify the constraints pls?
what about the size of node_to_visit_in_path? How big can that get.
Oh its a tree. I didn't realise it was a tree. Lets say u root the tree at 1, and u start at 1. Notice if u do a simple dfs, to visit all nodes in node_to_visit_in_path, and nothing more, and end up back at 1, u will get the minimum path for that route. (a route which starts at 1, visits all necessary vertices, and ends up back at 1). So now, instead of ending up at 1, u need to end up at N. This means, u just need to choose the last necessary vertex that u visit. I think the optimal choice is over all vertices which are either ancestors of N, or are in the subtree of N, the one with the highest depth. Call this node, opt_node. So the path is
Do a trivial dfs which starts at 1, and goes to all necessary nodes, but ends at opt_node. Then, go from opt_node -> N. This shldn't be too hard to implement which simple techniques like in/out time.
Im not 100% sure im right tho. So do double check.
Also notice, if there is no necessary vertex which is an ancestor, or in subtree of N. U do trivial dfs to visit all necessary nodes, end up back at 1, then go to N.
just dfs and check the path when you reach node N
aura
newbie + zero medalii oni aura
This is equal to 2*(total weight of edges in the smallest subtree that contains all nodes from the set, including 1 and N)-distance(1, N)
Can you please explain how, else any resources for this ** 2*(total weight of edges in the smallest subtree that contains all nodes from the set, including 1 and N)-distance(1, N)**
Steiner(minimal) subtree problems
Can't we just trim the tree leafs which don't need to be visited?? and then the remaining substree is our required subtree ? See this Cisco OA Question
yes exactly .... need to iterate up from the leafs and need to delete the every node below the first special node that must be visited as said in the problem ... also take 1 and N as such type of nodes ... We would never visit such nodes that don't have special nodes below it ! ... also if you want the path take care that you end up at the path of N at last walk.
https://mirror.codeforces.com/problemset/problem/1666/L How to approach this
While there is a leaf that doesn't need to be visited, delete it. You can do this using a single DFS or using a queue.
Now we must find the shortest 1--N path that visits every leaf.
An euler tour does this but is not the shortest. On it, the simple path from 1 to N is visited twice. We can easily piece the solution together out of substrings of the euler tour.