Problem:
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. Input 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. Output 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. Sample Input 4
1 2 3
10 20 30
10
1 2 2 1 5 5 1 8 8
10 1 1 20 1 1 30 1 1
3
1 1
1 1
0 Output for the Sample Input 80
136
2

Solution (Python):
from collections import deque
while 1:
    n = input()
    if n == 0:
        break
    P = map(int, raw_input().split())
    D = map(int, raw_input().split())
    U = [0]*n
    G = [[] for i in xrange(n)]
    for i in xrange(1, n):
        G[i].append((P[i-1]-1, D[i-1], i-1))
        G[P[i-1]-1].append((i, D[i-1], i-1))
    sum_D = sum(D)
    sum_path = sum_D
    for i in xrange(n):
        if len(G[i]) == 1:
            to, cost, r = G[i][0]
            if U[r] == 0:
                sum_path -= cost
                U[r] = 1
    def find(s):
        deq = deque()
        dist = [None]*n
        deq.append(s)
        dist[s] = 0
        while deq:
            v = deq.popleft()
            for t, c, r in G[v]:
                if dist[t] is None:
                    deq.append(t)
                    dist[t] = dist[v] + c
        ma = -1; result = None
        for i in xrange(n):
            if ma < dist[i] and len(G[i]) > 1:
                result = i
                ma = dist[i]
        return (result, ma)
    u = find(0)[0]
    if u is None:
        cost = 0
    else:
        v, cost = find(u)
    print sum_D + sum_path*2 - cost

Solution (Python):
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 = core_islands_num - 1
        diameter = 0
        end_point = start
        
        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
                    end_point = u
                if rest == 0:
                    break
                path.pop()
                bridge_lengths.pop()
    
        if turn:
            return diameter
        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()))
        
        end_bridges_weight = 0
        core_islands_num = n
        adj_list = [[] for i in range(n + 1)]
        s = 1
        for i1, i2, b_l in zip(range(2, n + 1), p, d):
            if i1 not in p[i1-1:]:
                end_bridges_weight += b_l
                core_islands_num -= 1
            else:
                s = i1
                adj_list[i1].append((i2, b_l))
                adj_list[i2].append((i1, b_l))
        if p.count(1) == 1:
            del adj_list[2][0]
            end_bridges_weight += d[0]
            core_islands_num -= 1
        
        e = dfs(s)
        dm = dfs(e, turn=True)
        
        ans = sum(d) * 3 - end_bridges_weight * 2 - dm
        print(ans)

solve()

Solution (Python):
def solve():
    from collections import deque
    def bfs(start):
        q = deque()
        q.append(start)
        
        unvisited = [True] * (n + 1)
        unvisited[start] = False
        
        distances = [0] * (n + 1)
        
        while q:
            x = q.popleft()
            for i, d in adj_list[x]:
                if unvisited[i]:
                    q.append(i)
                    unvisited[i] = False
                    distances[i] = distances[x] + d    
        
        max_d = max(distances)
        return (distances.index(max_d), max_d)
    
    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()))
        
        end_bridges_weight = 0
        adj_list = [[] for i in range(n + 1)]
        s = 0
        for i1, i2, b_l in zip(range(2, n + 1), p, d):
            if i1 not in p[i1-1:]:
                end_bridges_weight += b_l
            else:
                s = i1
                adj_list[i1].append((i2, b_l))
                adj_list[i2].append((i1, b_l))
        
        if p.count(1) == 1:
            del adj_list[2][0]
            end_bridges_weight += d[0]
        
        e, dm = bfs(s)
        e, dm = bfs(e)
        
        ans = sum(d) * 3 - end_bridges_weight * 2 - dm
        print(ans)

solve()

Solution (Python):


from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

while True:
    N = input()
    if N == 0:
        break
    p = map(int, raw_input().split())
    d = map(int, raw_input().split())
    E = [[] for i in range(N)]
    leaf = [False for i in range(N)]
    for i in range(N - 1):
        u = i + 1
        v = p[i] - 1
        cost = d[i]
        E[u].append((v, cost))
        E[v].append((u, cost))
    
    for i in range(N):
        leaf[i] = (len(E[i]) < 2)
    
    def func(num, pre, dist):
        if leaf[num]:
            return -1
        ret = (dist, num)
        for e in E[num]:
            if e[0] != pre:
                hoge = func(e[0], num, dist + e[1])
                if hoge != -1 and ret[0] < hoge[0]:
                    ret = hoge
        return ret

    for i in range(N):
        if not leaf[i]:
            ret = func(i, -1, 0)
            ret = func(ret[1], -1, 0)
            break
    ans = -2 * ret[0]
    for i in range(N):
        for e in E[i]:
            if leaf[i] or leaf[e[0]]:
                ans += e[1]
            else:
                ans += e[1] * 3
    print ans / 2

Solution (Python):


from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

while True:
    N = input()
    if N == 0:
        break
    p = map(int, raw_input().split())
    d = map(int, raw_input().split())
    E = [[] for i in range(N)]
    leaf = [False for i in range(N)]
    for i in range(N - 1):
        u = i + 1
        v = p[i] - 1
        cost = d[i]
        E[u].append((v, cost))
        E[v].append((u, cost))
    
    for i in range(N):
        leaf[i] = (len(E[i]) < 2)
    
    def func(num, pre, dist):
        if leaf[num]:
            return (0, 0)
        ret = (dist, num)
        for e in E[num]:
            if e[0] != pre:
                hoge = func(e[0], num, dist + e[1])
                if ret[0] < hoge[0]:
                    ret = hoge
        return ret

    for i in range(N):
        if not leaf[i]:
            ret = func(i, -1, 0)
            ret = func(ret[1], -1, 0)
            break
    ans = -2 * ret[0]
    for i in range(N):
        for e in E[i]:
            if leaf[i] or leaf[e[0]]:
                ans += e[1]
            else:
                ans += e[1] * 3
    print ans / 2

Solution (Python):
from sys import setrecursionlimit
setrecursionlimit(10 ** 8)

while True:
    n = int(input())
    if n == 0:
        break
    P = [int(i) for i in input().split()]
    D = [int(i) for i in input().split()]

    E = [list() for i in range(n + 1)]

    for i, (p, c) in enumerate(zip(P, D), 2):
        E[i].append((p, c))
        E[p].append((i, c))

    ans = 3 * sum(D)
    visited = [False] * (n + 1)
    is_leaf = [len(E[i]) == 1 for i in range(n + 1)]
    ans -= 2 * sum(E[i][0][1] for i in range(n + 1) if is_leaf[i])

    def dfs(i):
        visited[i] = True
        res = 0

        for e, c in E[i]:
            if is_leaf[e] or visited[e]:
                continue
            res = max(res, dfs(e) + c)

        return res    

    r = 0

    for i in range(1, n + 1):
        if is_leaf[i]:
            continue
        visited = [False] * (n + 1)
        r = max(r, dfs(i))

    print(ans - r)

Solution (Python):
from heapq import heappush, heappop
def dijkstra(s):
    d = [float("inf") for i in range(n)]
    d[s] = 0
    q = [(0,s)]
    while q:
        dx,x = heappop(q)
        for y,c in v[x]:
            if f[y] > 1:
                if dx+c < d[y]:
                    d[y] = dx+c
                    heappush(q,(d[y],y))
    return [-1 if d[i] == float("inf") else d[i] for i in range(n)]

while 1:
    n = int(input())
    if n == 0:
        break
    p = list(map(int,input().split()))
    d = list(map(int,input().split()))
    v = [[] for i in range(n)]
    edge = [None for i in range(n-1)]
    f = [0 for i in range(n)]
    for i in range(1,n):
        j = p[i-1]-1
        c = d[i-1]
        edge[i-1] = [j,i]
        v[i].append((j,c))
        v[j].append((i,c))
        f[i] += 1
        f[j] += 1
    ans = 0
    for x in range(n-1):
        i,j = edge[x]
        if f[i] == 1 or f[j] == 1:
            ans += d[x]
        else:
            ans += 3*d[x]
    dist = dijkstra(0)
    md = max(dist)
    l = dist.index(md)
    dist = dijkstra(l)
    m = max(dist)
    print(ans-m)

Solution (Python):
from collections import defaultdict, deque

while 1:
    n = int(input())
    if n == 0:
        break
    p = list(map(int, input().split()))
    d = list(map(int, input().split()))

    dic = defaultdict(int) 
    tree = [[] for i in range(n)]
    for i in range(n - 1):
        tree[i + 1].append(p[i]- 1)
        tree[p[i] - 1].append(i + 1)
        dic[(i + 1, p[i] - 1)] = d[i]
        dic[(p[i] - 1, i + 1)] = d[i]
    ans = 0
    de = []
    for num,i in enumerate(tree):
        if len(i) == 1:
            de.append((num,i[0]))
    for num, di in de:
        tree[num].remove(di)
        tree[di].remove(num)
        ans += dic[(num, di)]
    b = 0
    for i in range(n):
        check = [True] * n
        q = deque()
        q.append((i, 0))
        check[i] = False
        while q:
            now, di = q.pop()
            b = max(b, di)
            for k in tree[now]:
                if check[k]:
                    check[k] = False
                    q.append((k, di + dic[k, now]))
    print(sum(d)*3-2*ans-b)

Solution (Python):
while True:
    n = int(input())
    if n == 0:break
    plst = list(map(int, input().split()))
    dlst = list(map(int, input().split()))
    edges = [[] for _ in range(n)]
    for i in range(1, n):
        edges[i].append((plst[i - 1] - 1, dlst[i - 1]))
        edges[plst[i - 1] - 1].append((i, dlst[i - 1]))

    is_leaf = [len(edges[i]) == 1 for i in range(n)]
    INF = 10 ** 20


    def dist(x):
        dist_from_x = [-INF] * n
        dist_from_x[x] = 0
        checked = [False] * n
        checked[x] = True

        def search(x):
            for to, d in edges[x]:
                if is_leaf[to] or checked[to]:continue
                checked[to] = True
                dist_from_x[to] = dist_from_x[x] + d
                search(to)
        search(x)
        return dist_from_x

    for i in range(n):
        if not is_leaf[i]:
            dist_from_s = dist(i)
            break
    u = dist_from_s.index(max(dist_from_s))
    dist_from_u = dist(u)
    dia = max(dist_from_u)
    v = dist_from_u.index(dia)
    ans = sum(dlst) * 3
    for i in range(n):
        if len(edges[i]) == 1:
            ans -= edges[i][0][1] * 2
    print(ans - dia)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    def f(n):
        pa = LI()
        da = LI()
        e = collections.defaultdict(list)
        for i in range(n-1):
            a = i + 2
            b = pa[i]
            d = da[i]
            e[a].append((b,d))
            e[b].append((a,d))
        rf = collections.defaultdict(bool)
        s = None
        for k,v in e.items():
            if len(v) == 1:
                rf[k] = True
            else:
                s = k
        r = 0
        for k,v in e.items():
            for l,d in v:
                if k > l:
                    continue
                if rf[k] or rf[l]:
                    r += d
                else:
                    r += d * 3

        def search(s):
            d = collections.defaultdict(lambda: inf)
            d[s] = 0
            q = []
            heapq.heappush(q, (0, s))
            v = collections.defaultdict(bool)
            while len(q):
                k, u = heapq.heappop(q)
                if v[u]:
                    continue
                v[u] = True

                for uv, ud in e[u]:
                    if v[uv] or rf[uv]:
                        continue
                    vd = k + ud
                    if d[uv] > vd:
                        d[uv] = vd
                        heapq.heappush(q, (vd, uv))

            return d

        sd = search(s)
        sm = max(sd.values())
        for k,v in sd.items():
            if v == sm:
                s = k
        sd = search(s)
        sm = max(sd.values())

        return r - sm

    while 1:
        n = I()
        if n == 0:
            break
        rr.append(f(n))

    return '\n'.join(map(str,rr))


print(main())