computer_jock's blog

how to approach this problem ??
By computer_jock, history, 3 years ago, In English

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.

  • Vote: I like it
  • -3
  • Vote: I do not like it

Comments Comments (15)
| Write comment?
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can u specify the constraints pls?

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

what about the size of node_to_visit_in_path? How big can that get.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it -8 Vote: I do not like it

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.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

just dfs and check the path when you reach node N

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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)

→ Reply
  • »
    »
    11 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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)**

    → Reply
    • »
      »
      »
      11 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Steiner(minimal) subtree problems

      → Reply
      • »
        »
        »
        »
        10 months ago, hide # ^ |
        ← Rev. 3  
        Vote: I like it 0 Vote: I do not like it

        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

        → Reply
        • »
          »
          »
          »
          »
          10 months ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

https://mirror.codeforces.com/problemset/problem/1666/L How to approach this

→ Reply
»
2 years ago, hide # |
← Rev. 4  
Vote: I like it -16 Vote: I do not like it

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.

→ Reply