This one has two different linear-time solutions. Greedy and dynamic programming.

Greedy solution:
You should stop at the city with maximum distance from the root (city number 1). So all roads are traversed twice except for the roads between the root and this city.

Dynamic Programming:
For each city i we declare patrol[i] as the traverse needed for seeing i and all of it's children without having to come back to i (Children of a city are those cities adjacent to it which are farther from the root) and revpatrol[i] as the traverse needed to see all children of i and coming back to it. we can see that revpatrol[i] is sum of revpatrols of its children + sum of lengths of roads going from i to its children. patrol[i] can be found by replacing each of revpatrols with patrol and choosing their minimum.

• +7

 » 4 years ago, # | ← Rev. 3 →   0 please explain a bit about the dynamic programming approach for this problem...how can you traverse all the childs of i without traversing it again... suppose i has 2 branches then after travelling the first branch in graph, we must return to i to move to second branch.. thus how is patrol[i] is defined in those cases where the parent has more than 1 child.
•  » » 4 years ago, # ^ | ← Rev. 6 →   0 patrol[i] consists of all edges in its subtree twice, except for the edges in one of the branches, which get included only once. Code
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 .
 » 3 years ago, # |   0 It is not clear that how patrol[i] be calculated...Please explain in detail....
 » 21 month(s) ago, # |   0 The problem is quite interesting But i can't understand editorial Can anyone explain both greedy and dp approach in detail?
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   +8 If you are talking about eternal victory — Observation 1 : Optimal traversal always stops at any leaf. Observation 2 : All the edges from path to optimal leaf is always visited once and all other edges are visited twice because at any step we enter the subtree containig opt leaf after visiting all other subtree rooted at same depth. Do DP[node] = max length of path from node to any leaf in its subtree or just to a bfs.
 » 10 months ago, # |   0 I hope this helps.
•  » » 5 months ago, # ^ |   0 Nice approach