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

p2 p3 ... pn 

d2 d3 ... dn

The first integer n (3 &#8804; n &#8804; 800) is the number of the islands.
The islands are numbered from 1 to n.
The second line contains n-1 island numbers pi
(1 &#8804; pi < i), and tells that for each i
from 2 to n the island i and the island pi are connected by a bridge.
The third line contains n-1 integers di (1 &#8804; di &#8804; 100,000)
each denoting the length of the corresponding bridge.
That is, the length of the bridge connecting the island i and pi
is di. It takes di 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



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


Sample output:
80
136
2

Submission status: Wrong Answer

Solution code:
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()

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
#!/usr/bin/env 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

Submission status: Accepted

Solution code:
#!/usr/bin/env 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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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())

Submission status: Runtime Error

Solution code:
def dfs(start, frm, edges, mem):
    if mem[start]:
        return mem[start]

    round_trip = 0
    for dest, length in edges[start]:
        if dest == frm:
            continue

        dfs(dest, start, edges, mem)

        if len(edges[dest]) == 1:
            round_trip += length
            continue

        rt, _ = mem[dest]
        round_trip += length + rt + length + length

    one_way = round_trip
    for dest, length in edges[start]:
        if dest == frm:
            continue

        if len(edges[dest]) == 1:
            continue

        rt, ow = mem[dest]
        one_way = min(one_way, round_trip - rt - length + ow)

    mem[start] = (round_trip, one_way)
    return round_trip, one_way

    
def load():
    N = int(input())
    if N == 0:
        return None

    Ps = [int(p)-1 for p in input().split()]
    Ds = [int(d) for d in input().split()]

    edges = [[] for _ in range(N)]

    for i in range(N-1):
        p = Ps[i]
        d = Ds[i]
        i += 1
        edges[i].append((p, d))
        edges[p].append((i, d))
    return edges

def solve1(edges):
    N = len(edges)

    ans = 100000 * 800
    for i in range(N):
        mem = [None for _ in range(N)]
        _, one_way = dfs(i, -1, edges, mem)
        ans = min(ans, one_way)

    return ans

while True:
    edges = load()
    if edges is None:
        break
    print(solve1(edges))

Submission status: Runtime Error

Solution code:
def dfs(start, frm, edges, mem):
    if mem[start]:
        return mem[start]

    round_trip = 0
    for dest, length in edges[start]:
        if dest == frm:
            continue

        dfs(dest, start, edges, mem)

        if len(edges[dest]) == 1:
            round_trip += length
            continue

        rt, _ = mem[dest]
        round_trip += length + rt + length + length

    one_way = round_trip
    for dest, length in edges[start]:
        if dest == frm:
            continue

        if len(edges[dest]) == 1:
            continue

        rt, ow = mem[dest]
        one_way = min(one_way, round_trip - rt - length + ow)

    mem[start] = (round_trip, one_way)
    return round_trip, one_way

    
def load():
    N = int(input())
    if N == 0:
        return None

    Ps = [int(p)-1 for p in input().split()]
    Ds = [int(d) for d in input().split()]

    edges = [[] for _ in range(N)]

    for i in range(N-1):
        p = Ps[i]
        d = Ds[i]
        i += 1
        edges[i].append((p, d))
        edges[p].append((i, d))
    return edges

def solve1(edges):
    N = len(edges)

    ans = 100000 * 800 * 3
    for i in range(N):
        mem = [None for _ in range(N)]
        _, one_way = dfs(i, -1, edges, mem)
        ans = min(ans, one_way)

    return ans

while True:
    edges = load()
    if edges is None:
        break
    print(solve1(edges))

Submission status: Runtime Error

Solution code:
import time
time.sleep(120)
exit(0)

Submission status: Runtime Error

Solution code:
def calc_depth(x, k):
	global g, depth
	depth[x] = k
	for t in g[x].iterkeys():
		if(depth[t] == -1):
			calc_depth(t, k + 1)

def calc_dp(x):
	global g, depth
	s = 0; p = 0
	for t, c in g[x].iteritems():
		if depth[t] < depth[x]:
			continue		
		a, b = calc_dp(t)
		s += 3 * c + a if a else c
		p = max(p, c + a - b if a else 0)
	return s, s - p

while 1:
	n = input()
	if n == 0:
		break
	a = map(int, raw_input().split())
	b = map(int, raw_input().split())
	
	g = [{} for i in xrange(n)]
	for i in xrange(n - 1):
		p = i + 1; q = a[i] - 1; c = b[i]
		g[p][q] = g[q][p] = c

	ans = []
	for i in xrange(n):
		depth = [-1] * n
		calc_depth(i, 0)
		ans.append(calc_dp(i)[1])
	print min(ans)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10000)

def calc_depth(x, k):
	global g, depth
	depth[x] = k
	for t in g[x].iterkeys():
		if(depth[t] == -1):
			calc_depth(t, k + 1)

def calc_dp(x):
	global g, depth
	s = 0; p = 0
	for t, c in g[x].iteritems():
		if depth[t] < depth[x]:
			continue		
		a, b = calc_dp(t)
		s += 3 * c + a if a else c
		p = max(p, c + a - b if a else 0)
	return s, s - p

while 1:
	n = input()
	if n == 0:
		break
	a = map(int, raw_input().split())
	b = map(int, raw_input().split())
	
	g = [{} for i in xrange(n)]
	for i in xrange(n - 1):
		p = i + 1; q = a[i] - 1; c = b[i]
		g[p][q] = g[q][p] = c

	ans = []
	for i in xrange(n):
		depth = [-1] * n
		calc_depth(i, 0)
		ans.append(calc_dp(i)[1])
	print min(ans)

Submission status: Runtime Error

Solution code:
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
    file_input = open("1196_in_1", 'r')#
    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()