Problem:


Score : 700 points

Problem Statement

Takahashi found an undirected connected graph with N vertices and M edges. The vertices are numbered 1 through N. The i-th edge connects vertices a_i and b_i, and has a weight of c_i.

He will play Q rounds of a game using this graph. In the i-th round, two vertices S_i and T_i are specified, and he will choose a subset of the edges such that any vertex can be reached from at least one of the vertices S_i or T_i by traversing chosen edges.

For each round, find the minimum possible total weight of the edges chosen by Takahashi.

Constraints

1 ≦ N ≦ 4,000

1 ≦ M ≦ 400,000

1 ≦ Q ≦ 100,000

1 ≦ a_i,b_i,S_i,T_i ≦ N

1 ≦ c_i ≦ 10^{9}

a_i \neq b_i

S_i \neq T_i

The given graph is connected.

Partial Scores

In the test set worth 200 points, Q = 1.

In the test set worth another 300 points, Q ≦ 3000.

Input

The input is given from Standard Input in the following format:

N M
a_1 b_1 c_1
a_2 b_2 c_2
:
a_M b_M c_M
Q
S_1 T_1
S_2 T_2
:
S_Q T_Q

Output

Print Q lines. The i-th line should contain the minimum possible total weight of the edges chosen by Takahashi.

Sample Input 1

4 3
1 2 3
2 3 4
3 4 5
2
2 3
1 4

Sample Output 1

8
7

We will examine each round:

In the 1-st round, choosing edges 1 and 3 achieves the minimum total weight of 8.

In the 2-nd round, choosing edges 1 and 2 achieves the minimum total weight of 7.

Sample Input 2

4 6
1 3 5
4 1 10
2 4 6
3 2 2
3 4 5
2 1 3
1
2 3

Sample Output 2

8

This input satisfies the additional constraints for both partial scores.



Sample input:
4 3
1 2 3
2 3 4
3 4 5
2
2 3
1 4


Sample output:
8
7

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter

class Unionfindtree:
    def __init__(self, number):
        self.par = [i for i in range(number)]
        self.rank = [0] * (number)

    def find(self, x):  # 親を探す
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):  # x,yを繋げる
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.rank[px] < self.rank[py]:
            self.par[px] = py
        else:
            self.par[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1

    def connect(self, x, y):  # 親が同じかみる
        return self.find(x) == self.find(y)



N,M=map(int,input().split())
table=[[int(i) for i in input().split()]for i in range(M)]
Q=int(input())
query=[[int(i) for i in input().split()]for i in range(Q)]
if Q>1:
    sys.exit()
table = sorted(table,key=itemgetter(2))
T=Unionfindtree(N)
s,t=query[0]
s,t=s-1,t-1
T.union(s,t)
ans=0
for a,b,c in table:
    a,b=a-1,b-1
    if not T.connect(a,b):
        ans+=c
        T.union(a,b)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline


class Unionfindtree:
    def __init__(self, number):
        self.par = [i for i in range(number)]
        self.rank = [0] * (number)

    def find(self, x):  # 親を探す
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):  # x,yを繋げる
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.rank[px] < self.rank[py]:
            self.par[px] = py
        else:
            self.par[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1

    def connect(self, x, y):  # 親が同じかみる
        return self.find(x) == self.find(y)



N,M=map(int,input().split())
table=[]
for i in range(M):
    a,b,c=map(int,input().split())
    a,b=a-1,b-1
    table.append((c,a,b))
Q=int(input())
query=[]
for i in range(Q):
    s,t=map(int,input().split())
    s,t=s-1,t-1
    query.append((s,t))
if Q>1:
    sys.exit()
table.sort()
T=Unionfindtree(N)
s,t=query[0]
T.union(s,t)
ans=0
for c,a,b in table:
    if not T.connect(a,b):
        ans+=c
        T.union(a,b)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
n, m = map(int, raw_input().split())
sys.setrecursionlimit(10000)
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()
rn = range(n)
rnl = range(nl)
rnl1 = range(nl-1)
ps = [[0]*n for i in rnl]
cs = [[0]*n for i in rnl]
ds = [0]*n
INF = 10**9+7
p0 = ps[0]
c0 = cs[0]
def dfs(v, p, d):
    p0[v] = p
    c0[v] = dic[v,p]
    ds[v] = d
    for e in g[v]:
        if e!=p:dfs(e, v, d+1)
dfs(0, -1, 0)
for i in rnl1:
    p1 = ps[i+1]; p0 = ps[i]
    c1 = cs[i+1]; c0 = cs[i]
    for v in rn:
        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]])
cache = {}
def solve(u, v):
    if ds[u] > ds[v]:
        u,v = v,u
    if (u, v) in cache:
        return cache(u, v)
    res = 0
    du = ds[u]
    for k in rnl:
        if (ds[v] - du) >> k & 1:
            res = max(res, cs[k][v])
            v = ps[k][v]
    if u!=v:
        for k in reversed(rnl):
            pk = ps[k]
            if pk[u] != pk[v]:
                ck = cs[k]
                res = max(res, ck[u], ck[v])
                u = pk[u]; v = pk[v]
        res = max(res, c0[u], c0[v])
    cache[u, v] = cache[v, u] = res
    return res
q = input()
raw_input = sys.stdin.readline
while q:
    q -= 1
    s, t = map(int, raw_input().split())
    print su - solve(s-1, t-1)

Submission status: Wrong Answer

Solution code:
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]])
try:
    init(0)
except:
    exit(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)

Submission status: Wrong Answer

Solution code:
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]]
        if i:
            for v in xrange(n):
                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]
    return res

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

Submission status: Time Limit Exceeded

Solution code:
INF = 10**7
class PPUnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.time = [INF] * n
        self.number_time = [[0] for _ in [None] * n]
        self.number_dots = [[1] for _ in [None] * n]

    def find(self, x, t):
        while self.time[x] <= t:
            x = self.parents[x]
        return x

    def union(self, x, y, t):
        x = self.find(x, t)
        y = self.find(y, t)
        if x == y:
            return 0
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        self.number_time[x] += [t]
        self.number_dots[x] += [-self.parents[x]]
        self.time[y] = t
        return t

    def size(self, x, y, t):
        x = self.find(x, t)
        y = self.find(y, t)
        a = self.number_dots[x][bisect_left(self.number_time[x], t) - 1]
        if x != y:
            a += self.number_dots[y][bisect_left(self.number_time[y], t) - 1]
        return a

    def same(self, x, y, t = 0):
        if x == y:
            return t
        if self.time[x] == self.time[y] == INF:
            return -1
        if self.time[x] > self.time[y]:
            x, y = y, x
        return self.same(self.parents[x], y, self.time[x])

(n, m), *q = [[*map(int, o.split())] for o in open(0)]
UF = PPUnionFind(n)
ans = sum(UF.union(a - 1, b - 1, c) for a, b, c in sorted(q[:m], key = lambda t: t[2]))
for s, t in q[m+1:]:
    print(ans - UF.same(s - 1, t - 1))

Submission status: Time Limit Exceeded

Solution code:
INF = 10**7
class PPUnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.time = [INF] * n
        self.number_time = [[0] for _ in [None] * n]
        self.number_dots = [[1] for _ in [None] * n]

    def find(self, x, t):
        while self.time[x] <= t:
            x = self.parents[x]
        return x

    def union(self, x, y, t):
        x = self.find(x, t)
        y = self.find(y, t)
        if x == y:
            return 0
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        self.number_time[x] += [t]
        self.number_dots[x] += [-self.parents[x]]
        self.time[y] = t
        return 1

    def size(self, x, y, t):
        x = self.find(x, t)
        y = self.find(y, t)
        a = self.number_dots[x][bisect_left(self.number_time[x], t) - 1]
        if x != y:
            a += self.number_dots[y][bisect_left(self.number_time[y], t) - 1]
        return a

    def same(self, x, y, t = 0):
        if x == y:
            return t
        if self.time[x] == self.time[y] == INF:
            return -1
        if self.time[x] > self.time[y]:
            x, y = y, x
        return self.same(self.parents[x], y, self.time[x])

(n, m), *q = [[*map(int, o.split())] for o in open(0)]
UF = PPUnionFind(n)
E = sorted(q[:m], key = lambda t: t[2])
ans = 0
for a, b, c in E:
    if UF.union(a - 1, b - 1, c):
        ans += c
for s, t in q[m+1:]:
    print(ans - UF.same(s - 1, t - 1))

Submission status: Time Limit Exceeded

Solution code:
INF = 10**7
class PPUnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.time = [INF] * n
        self.number_time = [[0] for _ in [None] * n]
        self.number_dots = [[1] for _ in [None] * n]

    def find(self, x, t):
        while self.time[x] <= t:
            x = self.parents[x]
        return x

    def union(self, x, y, t):
        x = self.find(x, t)
        y = self.find(y, t)
        if x == y:
            return 0
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        self.number_time[x] += [t]
        self.number_dots[x] += [-self.parents[x]]
        self.time[y] = t
        return 1

    def size(self, x, y, t):
        x = self.find(x, t)
        y = self.find(y, t)
        a = self.number_dots[x][bisect_left(self.number_time[x], t) - 1]
        if x != y:
            a += self.number_dots[y][bisect_left(self.number_time[y], t) - 1]
        return a

    def same(self, x, y, t = 0):
        if x == y:
            return t
        if self.time[x] == self.time[y] == INF:
            return -1
        if self.time[x] > self.time[y]:
            x, y = y, x
        return self.same(self.parents[x], y, self.time[x])

(n, m), *q = [[*map(int, o.split())] for o in open(0)]
UF = PPUnionFind(n)
E = sorted(q[:m], key = lambda t: t[2])
ans = 0
for a, b, c in E:
    if UF.union(a - 1, b - 1, c):
        ans += c
for s, t in q[m+1:]:
    print(ans - UF.same(s - 1, t - 1))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
from collections import deque

class Unionfindtree:
    def __init__(self, number):
        self.par = [i for i in range(number)]
        self.rank = [0] * (number)

    def find(self, x):  # 親を探す
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):  # x,yを繋げる
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.rank[px] < self.rank[py]:
            self.par[px] = py
        else:
            self.par[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1

    def connect(self, x, y):  # 親が同じかみる
        return self.find(x) == self.find(y)

def dfs(s):
    H=deque()
    visit=[False]*N
    H.append((0,s))
    visit[s]=True
    L=[0]*N
    while H:
        pt,x=H.popleft()
        for y,cost in tree[x]:
            if visit[y]:
                continue
            c=max(cost,pt)
            H.append((c,y))
            visit[y]=True
            L[y]=c
    return L



N,M=map(int,input().split())
table=[[int(i) for i in input().split()]for i in range(M)]
Q=int(input())
query=[[int(i) for i in input().split()]for i in range(Q)]
table = sorted(table,key=itemgetter(2))
T=Unionfindtree(N)
#s,t=query[0]
#s,t=s-1,t-1
#T.union(s,t)
ans=0
tree=[[] for i in range(N)]
for i in range(M):
    a,b,c=table[i]
    a,b=a-1,b-1
    if not T.connect(a,b):
        ans+=c
        T.union(a,b)
        tree[a].append((b,c))
        tree[b].append((a,c))
M=[[0]*N for i in range(N)]
for i in range(N):
    M[i]=dfs(i)
for s,t in query:
    s,t=s-1,t-1
    print(ans-M[s][t])

Submission status: Time Limit Exceeded

Solution code:
inputs=lambda:map(int,raw_input().split())
n, m = inputs()
es = [inputs() for i in xrange(m)]
es.sort(key=lambda x:x[-1])
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 a, b, c 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]

Submission status: Time Limit Exceeded

Solution code:
inputs=lambda:map(int,raw_input().split())
n, m = inputs()
es = [inputs()[::-1] for i in xrange(m)]
es.sort()
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]

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

def solve():
    s, t = map(int, input().split())
    visited = [0] * N
    visited[s-1] = 1
    visited[t-1] = 1
    cost = 0

    vss = [v for v in range(N) if visited[v] == 1]
    vts = [v for v in range(N) if visited[v] == 0]
    while vts:
        mc = 10 ** 9 + 1
        mvt = None
        for vs in vss:
            for vt in vts:
                if edges[vs][vt] is not None and edges[vs][vt] < mc:
                    mc = edges[vs][vt]
                    mvt = vt
        vss.append(mvt)
        vts.remove(mvt)
        cost += mc
    return cost


N, M = map(int, input().split())

edges = [[None] * N for _ in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    edges[a-1][b-1] = c
    edges[b-1][a-1] = c

Q = int(input())
for i in range(Q):
    print(solve())

Submission status: Memory Limit Exceeded

Solution code:
import sys
n, m = map(int, raw_input().split())
sys.setrecursionlimit(10000)
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()+20
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)

Submission status: Memory Limit Exceeded

Solution code:
import sys
n, m = map(int, raw_input().split())
sys.setrecursionlimit(100000)
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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
from collections import deque

class Unionfindtree:
    def __init__(self, number):
        self.par = [i for i in range(number)]
        self.rank = [0] * (number)

    def find(self, x):  # 親を探す
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):  # x,yを繋げる
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.rank[px] < self.rank[py]:
            self.par[px] = py
        else:
            self.par[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1

    def connect(self, x, y):  # 親が同じかみる
        return self.find(x) == self.find(y)


N,M=map(int,input().split())
table=[[int(i) for i in input().split()]for i in range(M)]
Q=int(input())
query=[[int(i) for i in input().split()]for i in range(Q)]
table = sorted(table,key=itemgetter(2))
if N<3:
    for a,b in query:
        print(0)
    sys.exit()
T=Unionfindtree(N)
sear=Unionfindtree(2*N-1)
ans=0
value=[0]*(N+N-1)
dp=[[0]*(2*N-1) for i in range(16)]
table2=[[] for i in range(2*N-1)]
s=0
for i in range(M):
    a,b,c=table[i]
    a,b=a-1,b-1
    if not T.connect(a,b):
        ans+=c
        T.union(a,b)
        value[s+N]=c
        le=a
        ri=b
        for j in range(s+N,N-1,-1):
            if sear.connect(a,j):
                le=j
                break
        for j in range(s+N,N-1,-1):
            if sear.connect(b,j):
                ri=j
                break
        table2[s+N].append(le)
        table2[s+N].append(ri)
        sear.union(le,s+N)
        sear.union(ri,s+N)
        s+=1
    if s==N-1:
        break

H=deque()
H.append((0,2*N-2))
depth=[-1]*(2*N-1)
depth[2*N-2]=0
while H:
    dep,pt=H.popleft()
    for p in table2[pt]:
        H.append((dep+1,p))
        depth[p]=dep+1
        dp[0][p]=pt
#print(table2)
#print(depth,dp[0])

for k in range(1,16):
    for x in range(2*N-1):
        dp[k][x]=dp[k-1][dp[k-1][x]]
def LCA(s,t):
    if depth[s]>depth[t]:
        s,t=t,s
    for k in range(16):
        if ((depth[t]-depth[s] )>>k) & 1:
            t = dp[k][t]
    if s==t:
        return s
    for k in range(15,-1,-1):
        if dp[k][s]!=dp[k][t]:
            s=dp[k][s]
            t=dp[k][t]
    return dp[0][s]

for s,t in query:
    s,t=s-1,t-1
    pa=LCA(s,t)
    #print(pa,value[pa])
    print(ans-value[pa])

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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