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

| Write comment?
 » 7 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.
•  » » 7 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
 » 6 years ago, # |   0 It is not clear that how patrol[i] be calculated...Please explain in detail....
•  » » 3 years ago, # ^ |   -8 shut up
•  » » » 3 years ago, # ^ |   0 what he said
 » 5 years ago, # |   0 The problem is quite interesting But i can't understand editorial Can anyone explain both greedy and dp approach in detail?
•  » » 5 years 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.
 » 4 years ago, # |   0 I hope this helps.
 » 16 months ago, # |   0 Can anyone explain the dp solution a bit more? Is "patrol" and "repatrol" some standard term used in dp on tree problem? If yes then what is their concept?
 » 5 months ago, # |   0 #include using namespace std; void __print(int x) { cerr << x; } void __print(long x) { cerr << x; } void __print(long long x) { cerr << x; } void __print(unsigned x) { cerr << x; } void __print(unsigned long x) { cerr << x; } void __print(unsigned long long x) { cerr << x; } void __print(float x) { cerr << x; } void __print(double x) { cerr << x; } void __print(long double x) { cerr << x; } void __print(char x) { cerr << '\'' << x << '\''; } void __print(const char *x) { cerr << '\"' << x << '\"'; } void __print(const string &x) { cerr << '\"' << x << '\"'; } void __print(bool x) { cerr << (x ? "true" : "false"); } template void __print(const A &x); template void __print(const pair &p); template void __print(const tuple &t); template void __print(stack s); template void __print(queue q); template void __print(priority_queue q); template void __print(const A &x) { bool first = true; cerr << '{'; for (const auto &i : x) { cerr << (first ? "" : ","), __print(i); first = false; } cerr << '}'; } template void __print(const pair &p) { cerr << '('; __print(p.first); cerr << ','; __print(p.second); cerr << ')'; } template void __print(const tuple &t) { bool first = true; cerr << '('; apply([&first](const auto &...args) { ((cerr << (first ? "" : ","), __print(args), first = false), ...); }, t); cerr << ')'; } template void __print(stack s) { vector debugVector; while (!s.empty()) { T t = s.top(); debugVector.push_back(t); s.pop(); } reverse(debugVector.begin(), debugVector.end()); __print(debugVector); } template void __print(queue q) { vector debugVector; while (!q.empty()) { T t = q.front(); debugVector.push_back(t); q.pop(); } __print(debugVector); } template void __print(priority_queue q) { vector debugVector; while (!q.empty()) { T t = q.top(); debugVector.push_back(t); q.pop(); } __print(debugVector); } void _print() { cerr << "]\n"; } template void _print(const Head &H, const Tail &...T) { __print(H); if (sizeof...(T)) cerr << ", "; _print(T...); } #ifndef ONLINE_JUDGE #define debug(...) cerr << "Line:" << __LINE__ << " [" << #__VA_ARGS__ << "] = ["; _print(__VA_ARGS__) #else #define debug(...) #endif #define pyes cout << "YES\n"; #define pno cout << "NO\n"; #define int long long #define vi vector #define vvi vector> #define pb push_back #define ff first #define ss second #define rev(v) reverse(v.begin(), v.end()) #define srt(v) sort(v.begin(), v.end()) #define minv(v) *min_element(v.begin(), v.end()) #define maxv(v) *max_element(v.begin(), v.end()) #define all(v) v.begin(),v.end() #define in(x) int x; cin>>x; #define f(i,a,b) for(int i=a;i>a[i]; #define inpv(a,n) vector a; f(i,0,n) {int x; cin>>x; a.pb(x);} #define pr(x) cout< #define yoyo ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); int n = 3e5 + 5; vector adj(n);//we need to store the edge weights int ans = 0; void dfs(int node,int p,vector &d) { debug(node); debug(d); for(auto i : adj[node]) { if(i[0]!=p) { debug(i[1]); debug(d[node]); d[i[0]]=d[node]+i[1]; dfs(i[0],node,d); // d[i[0]]=d[p]+i[1]; } } } int32_t main() { cin>>n; int one_to_one=0; f(i,1,n){ int u,v,w; cin>>u>>v>>w; adj[u].pb({v,w}); adj[v].pb({u,w}); one_to_one+=2*w; } debug(one_to_one); vi d(n+1,0); d[1]=0; dfs(1,-1,d); debug(d); pr(one_to_one-maxv(d)); }