output_description: For each dataset, print the minimum time units required to remove all the
  bridges in a single line. Each line should not have any character other than
  this number.
input_description: The input consists of at most 100 datasets. Each dataset is formatted as
  follows.
  
  > _n_  
  >  _p_ 2 _p_ 3 ... _p n_  
  >  _d_ 2 _d_ 3 ... _d n_
  
  The first integer _n_ (3 ≤ _n_ ≤ 800) is the number of the islands. The
  islands are numbered from 1 to _n_. The second line contains _n_ -1 island
  numbers _p i_ (1 ≤ _p i_ < _i_), and tells that for each _i_ from 2 to _n_ the
  island _i_ and the island _p i_ are connected by a bridge. The third line
  contains _n_ -1 integers _d i_ (1 ≤ _d i_ ≤ 100,000) each denoting the length
  of the corresponding bridge. That is, the length of the bridge connecting the
  island _i_ and _p i_ is _d i_. It takes _d i_ units of time to cross the
  bridge, and also the same units of time to remove it. Note that, with this
  input format, it is assured that all the islands are reachable each other by
  crossing one or more bridges.
  
  The input ends with a line with a single zero.
attempt: def solve():
      from collections import deque
  
      def dfs(start, turn=False):
          path = deque()
          path.append(start)
  
          bridge_lengths = deque()
          bridge_lengths.append(0)
  
          unvisited = [True] * (n + 1)
          unvisited[start] = False
  
          rest = n - 1
          diameter = 0
  
          while True:
              u = path[-1]
              for i, d in adj_list[u]:
                  if unvisited[i]:
                      path.append(i)
                      unvisited[i] = False
                      rest -= 1
                      bridge_lengths.append(d)
                      break
              else:
                  distance = sum(bridge_lengths)
                  if diameter < distance:
                      diameter = distance
                      ans = diameter - bridge_lengths[1] - bridge_lengths[-1]
                      end_point = u
                  if rest == 0:
                      break
                  path.pop()
                  bridge_lengths.pop()
  
          if turn:
              return ans
          else:
              return end_point
  
      import sys
  
      file_input = sys.stdin
      while True:
          n = int(file_input.readline())
          if n == 0:
              break
  
          p = list(map(int, file_input.readline().split()))
          d = list(map(int, file_input.readline().split()))
  
          adj_list = [[] for i in range(n + 1)]
          end_bridges_weight = 0
          for i1, i2, b_l in zip(range(2, n + 1), p, d):
              adj_list[i1].append((i2, b_l))
              adj_list[i2].append((i1, b_l))
              if i1 not in p[i1 - 1 :]:
                  end_bridges_weight += b_l
  
          if p.count(1) == 1:
              end_bridges_weight += d[0]
  
          e = dfs(1)
          d_m = dfs(e, turn=True)
  
          ans = sum(d) * 3 - end_bridges_weight * 2 - d_m
          print(ans)
  
  
  solve()
  
problem_description: Bridge Removal
  
  ICPC islands once had been a popular tourist destination. For nature
  preservation, however, the government decided to prohibit entrance to the
  islands, and to remove all the man-made structures there. The hardest part of
  the project is to remove all the bridges connecting the islands.
  
  There are _n_ islands and _n_ -1 bridges. The bridges are built so that all
  the islands are reachable from all the other islands by crossing one or more
  bridges. The bridge removal team can choose any island as the starting point,
  and can repeat either of the following steps.
  
    * Move to another island by crossing a bridge that is connected to the current island.
    * Remove one bridge that is connected to the current island, and stay at the same island after the removal.
  
  Of course, a bridge, once removed, cannot be crossed in either direction.
  Crossing or removing a bridge both takes time proportional to the length of
  the bridge. Your task is to compute the shortest time necessary for removing
  all the bridges. Note that the island where the team starts can differ from
  where the team finishes the work.
samples: [{"input": "1 2 3\n    10 20 30\n    10\n    1 2 2 1 5 5 1 8 8\n    10 1 1 20 1 1 30 1 1\n    3\n    1 1\n    1 1\n    0", "output": "136\n    2"}]