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.
Auto comment: topic has been updated by computer_jock (previous revision, new revision, compare).
Auto comment: topic has been updated by computer_jock (previous revision, new revision, compare).
Can u specify the constraints pls?
n upto 1e5
Auto comment: topic has been updated by computer_jock (previous revision, new revision, compare).
Auto comment: topic has been updated by computer_jock (previous revision, new revision, compare).
what about the size of node_to_visit_in_path? How big can that get.
n-1 nodes
Auto comment: topic has been updated by computer_jock (previous revision, new revision, compare).
Auto comment: topic has been updated by computer_jock (previous revision, new revision, compare).
Auto comment: topic has been updated by computer_jock (previous revision, new revision, compare).
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.
I think I solved a similar ( I think actually the same some time ago), the idea is to do a simple DFS and keep accounting for the essential vertex(the nodes that you must visit), start from 1 let's say you encounter your first essential vertex add twice the distance travelled into the answer(why twice, since you need to come to this vertex from 1 and go back again, except in the case of N where you just need to go, so just add once for N), now reinitialise the distance to 0, again continue the DFS, if you encounter another essential vertex add twice again, let me know if this is clear
Yes there is a similar question in LeetCode : 1443. Minimum Time to Collect All Apples in a Tree. The solution is similar to what you have described, you can consider the last node, that is, the Nth node as part of the apple array as well and while returning for the Nth node return +1 instead of +2.
just dfs and check the path when you reach node N
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)
Yes this is correct ig but we need to subtract the edges that don't need to be counted for example in the smallest subtree if after once vertex which we must visit in the subtree of that vertex there is no other vertex we must visit no need to add that in the answer
https://codeforces.com/problemset/problem/1666/L How to approach this
Yes, this is a very good question. See the algorithm: - First, find the path from 1 to N. (Here 1->3->5) - Make new visited array with visited[node]=1 for node in path and rest 0. - For each node in the path: Get the minimum distance needed to be traversed to visit all nodes in node_to_visit_in_path individually.
Answer: (size of path — 1) + minimum distances from all nodes traversed above.
In the given test case, after finding path, you will traverse for a minimum distance for nodes 1, 3, and 5 individually. Answers of individual minimum distance will be: Node 1: 2 (Going to 2 and coming back to 1) Node 3: 2 (Going to 4 and coming back to 3) Node 5: 0 (No way out)
To find minimum distances from all nodes in path: See this. Just consider your current node as 0 w.r.t. problem given in the link. (Remember to mark nodes of path as visited before doing this) Thanks :)
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.