Problem p03903 (python)

Fixed submission:
from collections import deque
import sys
sys.setrecursionlimit(10**5)

N, M = map(int, input().split())
E = []
for i in range(M):
    a, b, c = map(int, input().split())
    E.append((c, a-1, b-1))
E.sort()

*p, = range(N)
def root(x):
    if x == p[x]:
        return x
    p[x] = y = root(p[x])
    return y

L = 2*N-1
G = [[]] * L
C = [0]*L
*lb, = range(N)
cur = N

s = 0
for c, a, b in E:
    pa = root(a); pb = root(b)
    if pa == pb:
        continue
    s += c
    chds = [lb[pa], lb[pb]]
    if pa < pb:
        p[pb] = pa
        lb[pa] = cur
    else:
        p[pa] = pb
        lb[pb] = cur
    C[cur] = c
    G[cur] = chds
    cur += 1

H = [0]*L
prv = [-1]*L
def dfs(v):
    s = 1; heavy = -1; m = 0
    for w in G[v]:
        prv[w] = v
        c = dfs(w)
        if m < c:
            heavy = w
            m = c
        s += c
    H[v] = heavy
    return s
dfs(L-1)

SS = []
D = []
LB = [0]*L
I = [0]*L
que = deque([(L-1, 0)])
while que:
    v, d = que.popleft()
    S = []
    k = len(SS)
    while v != -1:
        I[v] = len(S)
        S.append(v)
        LB[v] = k
        h = H[v]
        for w in G[v]:
            if h == w:
                continue
            que.append((w, d+1))
        v = h
    SS.append(S)
    D.append(d)


def query(u, v):
    lu = LB[u]; lv = LB[v]
    dd = D[lv] - D[lu]
    if dd < 0:
        lu, lv = lv, lu
        v, u = u, v
        dd = -dd

    for _ in range(dd):
        v = prv[SS[lv][0]]
        lv = LB[v]

    while lu != lv:
        u = prv[SS[lu][0]]
        lu = LB[u]

        v = prv[SS[lv][0]]
        lv = LB[v]

    return u if I[u] < I[v] else v


def gen():
    Q = int(input())
    for i in range(Q):
        u, v = map(int, input().split())
        w = query(u-1, v-1)
        yield "%d\n" % (s - C[w])
ans = list(gen())
sys.stdout.writelines(ans)

Buggy submission (verdict: Runtime Error):
inputs=lambda:map(int,raw_input().split())
n, m = inputs()
es = [inputs() for i in xrange(m)]
es.sort(key=lambda x:x[2])
parent = range(n+1)
def root(x):
    if x == parent[x]:
        return x
    parent[x] = root(parent[x])
    return parent[x]
def unite(x, y):
    px = root(x)
    py = root(y)
    if px < py:
        parent[py] = px
    else:
        parent[px] = py
su = 0
g = [[] for i in xrange(n+1)]
for c, a, b in es:
    if root(a) != root(b):
        unite(a, b)
        su += c
        g[a].append((b, c))
        g[b].append((a, c))

import sys
sys.setrecursionlimit(100000)
dic = {}
def dfs(s, v, prev, cost):
    dic[s,v] = cost
    for e, c in g[v]:
        if prev != e:
            dfs(s, e, v, max(cost, c))
for i in xrange(n):
    dfs(i+1, i+1, -1, 0)
for i in xrange(input()):
    s, t = inputs()
    print su-dic[s,t]

Buggy submission (verdict: Runtime Error):
n, m = map(int, raw_input().split())
que = []
for i in xrange(m):
    a, b, c = map(int, raw_input().split())
    que.append((c, a, b))
que.sort()
p = range(n)
def root(x):
    if x!=p[x]: x=p[x]=root(p[x])
    return x
def unite(x, y):
    px = p[x]
    py = p[y]
    if px < py:
        p[py] = px
    else:
        p[px] = py
su = 0
g = [[] for i in xrange(n)]
dic = {(0, -1): 0}
for c, a, b in que:
    a -= 1; b -= 1
    if root(a) != root(b):
        unite(a, b)
        su += c
        g[a].append(b)
        g[b].append(a)
        dic[a, b] = dic[b, a] = c

nl = n.bit_length()
ps = [[0]*n for i in xrange(nl)]
cs = [[0]*n for i in xrange(nl)]
ds = [0]*n
INF = 10**9+7
def dfs(v, p, d):
    ps[0][v] = p
    cs[0][v] = dic[v,p]
    ds[v] = d
    for e in g[v]:
        if e!=p:dfs(e, v, d+1)
def init(s):
    dfs(s, -1, 0)
    for i in xrange(nl-1):
        p1 = ps[i+1]; p0 = ps[i]
        c1 = cs[i+1]; c0 = cs[i]
        for v in xrange(n):
            p1[v] = -1 if p0[v] < 0 else p0[p0[v]]
            c1[v] = INF if p0[v] < 0 else max(c0[v], c0[p0[v]])
init(0)
def solve(u, v):
    res = 0
    if ds[u] > ds[v]:
        u,v = v,u
    for k in xrange(nl-1):
        if (ds[v] - ds[u]) >> k & 1:
            res = max(res, cs[k][v])
            v = ps[k][v]
    if u==v: return res
    for k in xrange(nl-1, -1, -1):
        pk = ps[k]
        if pk[u] != pk[v]:
            res = max(res, cs[k][u], cs[k][v])
            u = pk[u]; v = pk[v]
    res = max(res, cs[0][u], cs[0][v])
    return res

for i in xrange(input()):
    s, t = map(int, raw_input().split())
    try:
        print su - solve(s-1, t-1)
    except:
        exit(0)

Buggy submission (verdict: Runtime Error):
n, m = map(int, raw_input().split())
que = []
for i in xrange(m):
    a, b, c = map(int, raw_input().split())
    que.append((c, a, b))
que.sort()
p = range(n)
def root(x):
    if x!=p[x]: x=p[x]=root(p[x])
    return x
def unite(x, y):
    px = p[x]
    py = p[y]
    if px < py:
        p[py] = px
    else:
        p[px] = py
su = 0
g = [[] for i in xrange(n)]
dic = {(0, -1): 0}
for c, a, b in que:
    a -= 1; b -= 1
    if root(a) != root(b):
        unite(a, b)
        su += c
        g[a].append(b)
        g[b].append(a)
        dic[a, b] = dic[b, a] = c

nl = n.bit_length()
ps = [[0]*n for i in xrange(nl)]
cs = [[0]*n for i in xrange(nl)]
ds = [0]*n
INF = 10**9+7
def dfs(v, p, d):
    ps[0][v] = p
    cs[0][v] = dic[v,p]
    ds[v] = d
    for e in g[v]:
        if e!=p:dfs(e, v, d+1)
def init(s):
    dfs(s, -1, 0)
    for i in xrange(nl-1):
        p1 = ps[i+1]; p0 = ps[i]
        c1 = cs[i+1]; c0 = cs[i]
        for v in xrange(n):
            p1[v] = -1 if p0[v] < 0 else p0[p0[v]]
            c1[v] = INF if p0[v] < 0 else max(c0[v], c0[p0[v]])
init(0)
def solve(u, v):
    res = 0
    if ds[u] > ds[v]:
        u,v = v,u
    for k in xrange(nl-1):
        if (ds[v] - ds[u]) >> k & 1:
            res = max(res, cs[k][v])
            v = ps[k][v]
    if u==v: return res
    for k in xrange(nl-1, -1, -1):
        pk = ps[k]
        if pk[u] != pk[v]:
            res = max(res, cs[k][u], cs[k][v])
            u = pk[u]; v = pk[v]
    res = max(res, cs[0][u], cs[0][v])
    return res

for i in xrange(input()):
    s, t = map(int, raw_input().split())
    print su - solve(s-1, t-1)

Buggy submission (verdict: Runtime Error):
n, m = map(int, raw_input().split())
que = []
for i in xrange(m):
    a, b, c = map(int, raw_input().split())
    que.append((c, a, b))
que.sort()
p = range(n)
def root(x):
    if x!=p[x]: x=p[x]=root(p[x])
    return x
def unite(x, y):
    px = p[x]
    py = p[y]
    if px < py:
        p[py] = px
    else:
        p[px] = py
su = 0
g = [[] for i in xrange(n)]
dic = {(0, -1): 0}
for c, a, b in que:
    a -= 1; b -= 1
    if root(a) != root(b):
        unite(a, b)
        su += c
        g[a].append(b)
        g[b].append(a)
        dic[a, b] = dic[b, a] = c

nl = n.bit_length()
ps = [[0]*n for i in xrange(nl)]
cs = [[0]*n for i in xrange(nl)]
ds = [0]*n
INF = 10**9+7
def dfs(v, p, d):
    ps[0][v] = p
    cs[0][v] = dic[v,p]
    ds[v] = d
    for e in g[v]:
        if e!=p:dfs(e, v, d+1)
def init(s):
    dfs(s, -1, 0)
    for i in xrange(nl-1):
        p1 = ps[i+1]; p0 = ps[i]
        c1 = cs[i+1]; c0 = cs[i]
        for v in xrange(n):
            p1[v] = -1 if p0[v] < 0 else p0[p0[v]]
            c1[v] = INF if c0[v] == INF else max(c0[v], c0[p0[v]])
init(0)
def solve(u, v):
    res = 0
    if ds[u] > ds[v]:
        u,v = v,u
    for k in xrange(nl-1):
        if (ds[v] - ds[u]) >> k & 1:
            res = max(res, cs[k][v])
            v = ps[k][v]
    if u==v: return res
    for k in xrange(nl-1, -1, -1):
        pk = ps[k]
        if pk[u] != pk[v]:
            res = max(res, cs[k][u], cs[k][v])
            u = pk[u]; v = pk[v]
    res = max(res, cs[0][u], cs[0][v])
    return res

for i in xrange(input()):
    s, t = map(int, raw_input().split())
    print su - solve(s-1, t-1)

Buggy submission (verdict: Runtime Error):
k = input()
s = raw_input()

left = 0; right = int(s)
while 1:
    mid = (left + right) / 2
    cnt = 0
    now = 0
    for c in s:
        now = 10*now + int(c)
        if now > mid:
            cnt += 1
            now = int(c)
            if now > mid:
                cnt = 100003
                break
    if cnt > k:
        if left == mid:
            break
        left = mid
    else:
        if right == mid:
            break
        right = mid
print left+1