Guest User

CBR57 problem D

a guest
Feb 22nd, 2011
107
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. n = input ()
  2. g = [[] for _ in xrange (n)]
  3. s = 0
  4. for _ in xrange (n - 1):
  5.     u, v, w = map (int, raw_input ().split ())
  6.     u -= 1
  7.     v -= 1
  8.     g[u].append ([v, w])
  9.     g[v].append ([u, w])
  10.     s += w
  11.  
  12. def dfs (u, p, W):
  13.     res = W    
  14.     for v, w in g[u]:
  15.         if v != p:
  16.             res = max (res, dfs (v, u, W + w))
  17.     return res
  18.  
  19. print 2 * s - dfs (0, -1, 0)
RAW Paste Data