Solution 4 for Scaler Topics Fortnightly Contest

Transform Your Career

Choose from our industry-leading programs designed for career success

NSDC Certified

Master full-stack development with AI integration

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

NSDC Certified

Advanced data science techniques with AI specialization

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

NSDC Certified

Deep dive into AIML with focus on Agentic systems

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

NSDC Certified

Build and manage AI-powered cloud infrastructure

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

NSDC Certified

Premier AI engineering certification from IIT-Roorkee

3 MonthsDuration

AI-LedCurriculum

Career SupportSupport

Note that we dont have to come back to the warehouse again once we visit the last package.
Say if the problem was that we had to go back to the warehouse after delivering all packages can you solve the problem?
Think if you can use that to solve the original problem.
Say tot is the answer if we had to go back to the warehouse after all deliveries, then if a subtree has a package to be delivered, then tot += 2 * W where W is the cost of the edge from the parent of the subtree to that subtree that is once for entering the subtree and once for leaving the subtree. Now we dont have to go back to the warehouse after we deliver the last node then its simple choose the last node which is the farthest from the warehouse that way you will save the most distance. So ans = tot - max of depth of all package nodes.

Time Complexity - O(N)

Space Complexity - O(N)