Problem:


Score : 900 points

Problem Statement

We have an undirected weighted graph with N vertices and M edges.
The i-th edge in the graph connects Vertex U_i and Vertex V_i, and has a weight of W_i.
Additionally, you are given an integer X.

Find the number of ways to paint each edge in this graph either white or black such that the following condition is met, modulo 10^9 + 7:

The graph has a spanning tree that contains both an edge painted white and an edge painted black. Furthermore, among such spanning trees, the one with the smallest weight has a weight of X.

Here, the weight of a spanning tree is the sum of the weights of the edges contained in the spanning tree.

Constraints

1 \leq N \leq 1 000

1 \leq M \leq 2 000

1 \leq U_i, V_i \leq N (1 \leq i \leq M)

1 \leq W_i \leq 10^9 (1 \leq i \leq M)

If i \neq j, then (U_i, V_i) \neq (U_j, V_j) and (U_i, V_i) \neq (V_j, U_j).

U_i \neq V_i (1 \leq i \leq M)

The given graph is connected.

1 \leq X \leq 10^{12}

All input values are integers.

Input

Input is given from Standard Input in the following format:

N M
X
U_1 V_1 W_1
U_2 V_2 W_2
:
U_M V_M W_M

Output

Print the answer.

Sample Input 1

3 3
2
1 2 1
2 3 1
3 1 1

Sample Output 1

6

Sample Input 2

3 3
3
1 2 1
2 3 1
3 1 2

Sample Output 2

2

Sample Input 3

5 4
1
1 2 3
1 3 3
2 4 6
2 5 8

Sample Output 3

0

Sample Input 4

8 10
49
4 6 10
8 4 11
5 8 9
1 8 10
3 8 128773450
7 8 10
4 2 4
3 4 1
3 1 13
5 2 2

Sample Output 4

4



Sample input:
3 3
2
1 2 1
2 3 1
3 1 1


Sample output:
6

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter


class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self._root(self.table[x])
            return self.table[x]

    def find(self, x, y):
        return self._root(x) == self._root(y)

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1


class LcaDoubling:
    """
    links[v] = { (u, w), (u, w), ... }  (u:隣接頂点, w:辺の重み)
    というグラフ情報から、ダブリングによるLCAを構築。
    任意の2頂点のLCAおよび「パスに含まれる最長辺の長さ」を取得できるようにする
    """

    def __init__(self, n, links, root=0):
        self.depths = [-1] * n
        self.max_paths = [[-1] * (n + 1)]
        self.ancestors = [[-1] * (n + 1)]  # 頂点数より1個長くし、存在しないことを-1で表す。末尾(-1)要素は常に-1
        self._init_dfs(n, links, root)

        prev_ancestors = self.ancestors[-1]
        prev_max_paths = self.max_paths[-1]
        max_depth = max(self.depths)
        d = 1
        while d < max_depth:
            next_ancestors = [prev_ancestors[p] for p in prev_ancestors]
            next_max_paths = [max(prev_max_paths[p], prev_max_paths[q]) for p, q in enumerate(prev_ancestors)]
            self.ancestors.append(next_ancestors)
            self.max_paths.append(next_max_paths)
            d <<= 1
            prev_ancestors = next_ancestors
            prev_max_paths = next_max_paths

    def _init_dfs(self, n, links, root):
        q = [(root, -1, 0, 0)]
        direct_ancestors = self.ancestors[0]
        direct_max_paths = self.max_paths[0]
        while q:
            v, p, dep, max_path = q.pop()
            direct_ancestors[v] = p
            self.depths[v] = dep
            direct_max_paths[v] = max_path
            q.extend((u, v, dep + 1, w) for u, w in links[v] if u != p)
        return direct_ancestors

    def get_lca_with_max_path(self, u, v):
        du, dv = self.depths[u], self.depths[v]
        if du > dv:
            u, v = v, u
            du, dv = dv, du
        tu = u
        tv, max_path = self.upstream(v, dv - du)
        if u == tv:
            return u, max_path
        for k in range(du.bit_length() - 1, -1, -1):
            mu = self.ancestors[k][tu]
            mv = self.ancestors[k][tv]
            if mu != mv:
                max_path = max(max_path, self.max_paths[k][tu], self.max_paths[k][tv])
                tu = mu
                tv = mv
        lca = self.ancestors[0][tu]
        assert lca == self.ancestors[0][tv]
        max_path = max(max_path, self.max_paths[0][tu], self.max_paths[0][tv])
        return lca, max_path

    def upstream(self, v, k):
        i = 0
        mp = 0
        while k:
            if k & 1:
                mp = max(mp, self.max_paths[i][v])
                v = self.ancestors[i][v]
            k >>= 1
            i += 1
        return v, mp


def construct_spanning_tree(n, uvw):
    uft = UnionFind(n)
    spanning_links = [set() for _ in range(n)]
    not_spanning_links = []
    adopted_count = 0
    adopted_weight = 0
    i = 0
    while adopted_count < n - 1:
        u, v, w = uvw[i]
        if uft.find(u, v):
            not_spanning_links.append(uvw[i])
        else:
            spanning_links[u].add((v, w))
            spanning_links[v].add((u, w))
            uft.union(u, v)
            adopted_count += 1
            adopted_weight += w
        i += 1
    not_spanning_links.extend(uvw[i:])
    return adopted_weight, spanning_links, not_spanning_links


def solve(n, m, x, uvw):
    # 最小全域木(MST)のコスト総和がXと一致するなら、MSTに白黒含めれば良い（ただし同率の辺は考慮）
    # そうでないなら、MST以外の辺を使えるのはせいぜい1本まで→各辺の取り替えコスト増加分を見る
    # MST以外の辺(u, v)を採用する際に代わりに除かれる辺は、MST上で{u, v}を結ぶパスの最大コスト辺

    mst_weight, spanning_links, not_spanning_links = construct_spanning_tree(n, uvw)
    # print(mst_weight)
    # print(spanning_links)
    # print(not_spanning_links)
    if x < mst_weight:
        return 0
    diff = x - mst_weight
    lcad = LcaDoubling(n, spanning_links)

    lower_count, exact_count, upper_count = 0, 0, 0
    for u, v, w in not_spanning_links:
        lca, mp = lcad.get_lca_with_max_path(u, v)
        inc = w - mp
        # print(u, v, w, lca, mp, inc)
        if inc < diff:
            lower_count += 1
        elif inc > diff:
            upper_count += 1
        else:
            exact_count += 1

    MOD = 10 ** 9 + 7
    # x >= mst_weight の場合、MSTの辺は全て同じ色として
    # lower_count も全てそれと同じ色
    # exact_count は「全てがMSTと同じ色」でない限りどのような塗り方でもよい
    # upper_count はどのような塗り方でもよい
    replace_to_exact_link = 2 * (pow(2, exact_count, MOD) - 1) * pow(2, upper_count, MOD) % MOD
    if diff > 0:
        return replace_to_exact_link

    # x == mst_weight の場合は、MSTが全て同じ色でない限りどのような塗り方でもよいパターンも追加
    use_first_spanning = (pow(2, n - 1, MOD) - 2) * pow(2, m - n + 1, MOD) % MOD
    return (use_first_spanning + replace_to_exact_link) % MOD


n, m = map(int, input().split())
x = int(input())
uvw = []
for line in sys.stdin:
    u, v, w = map(int, line.split())
    u -= 1
    v -= 1
    uvw.append((u, v, w))
uvw.sort(key=itemgetter(2))
print(solve(n, m, x, uvw))

Submission status: Accepted

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

def find_parent(x):
    y=parent[x]
    if y<0:
        return x
    parent[x]=find_parent(y)
    return parent[x]

def connect(a,b):
    c=find_parent(a)
    d=find_parent(b)
    if c==d:
        return
    if parent[c]<parent[d]:
        parent[c]+=parent[d]
        parent[d]=c
    else:
        parent[d]+=parent[c]
        parent[c]=d
    return

def f(S,G):
    que=[S]
    flag=[0]*(N+1)
    L=[0]*(N+1)
    flag[S]=1
    while que:
        H=[]
        for u in que:
            for v,l in data[u]:
                if flag[v]==0:
                    flag[v]=u
                    L[v]=l
                    H.append(v)
                if v==G:
                    break
            else:
                continue
            break
        else:
            que=H
            continue
        break
    qqq=0
    que=G
    while que!=S:
        qqq=max(qqq,L[que])
        que=flag[que]
    return qqq

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

inf=float("inf")
mod=10**9+7

edge=[]
for i in range(M):
    U,V,W=map(int,input().split())
    edge.append([W,U,V])
edge.sort()
parent=[-1]*(N+1)

remain_edge=[]
data=[[] for i in range(N+1)]
weigh=0

for l,a,b in edge:
    if find_parent(a)==find_parent(b):
        remain_edge.append([l,a,b])
        continue
    else:
        connect(a,b)
        weigh+=l
        data[a].append([b,l])
        data[b].append([a,l])
        
if weigh>X:
    print(0)
    sys.exit()
elif weigh==X:
    count=N-1
    for l,a,b in remain_edge:
        if l==f(a,b):
            count+=1
    print(pow(2,M-count,mod)*(pow(2,count,mod)-2)%mod)
else:
    count_1=0
    count_2=0
    count_3=0
    for l,a,b in remain_edge:
        if weigh-f(a,b)+l==X:
            count_1+=1
        elif weigh-f(a,b)+l<X:
            count_2+=1
        else:
            count_3+=1
    print(2*pow(2,count_3,mod)*(pow(2,count_1,mod)-1)%mod)

Submission status: Accepted

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

sys.setrecursionlimit(2*10**6)
class UF():
    def __init__(self, num):
        self.par = [-1]*num
        self.size = [1]*num
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            x = self.par[x]
            return self.find(x)
    
    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            if self.par[rx] < self.par[ry]:
                self.par[ry] = rx
                self.size[rx] += self.size[ry] 
            elif self.par[rx] > self.par[ry]:
                self.par[rx] = ry
                self.size[ry] += self.size[rx]
            else:
                self.par[rx] -= 1
                self.par[ry] = rx
                self.size[rx] += self.size[ry]
        return

def parorder(Edge, p):
    N = len(Edge)
    Cs = [None]*N
    par = [0]*N
    par[p] = -1
    stack = [p]
    order = []
    visited = set([p])
    ast = stack.append
    apo = order.append
    while stack:
        vn = stack.pop()
        apo(vn)
        for vf, cost in Edge[vn]:
            if vf in visited:
                continue
            visited.add(vf)
            par[vf] = vn
            Cs[vf] = cost
            ast(vf)
    return par, order, Cs

def getcld(p):
    res = [[] for _ in range(len(p))]
    for i, v in enumerate(p[1:], 1):
        res[v].append(i)
    return res

MOD = 10**9+7
N, M = map(int, readline().split())
X = int(readline())
Edge = []
for _ in range(M):
    a, b, c = map(int, readline().split())
    a -= 1
    b -= 1
    Edge.append((c, a, b))

Edge.sort(key = itemgetter(0))

T = UF(N)

cnt = 0
idx = 0
tEdge = [[] for _ in range(N)]
oEdge = []
mst = 0
while cnt < N-1:
    while True:
        cost, x, y = Edge[idx]
        rx = T.find(x)
        ry = T.find(y)
        idx += 1
        if rx != ry:
            break
        oEdge.append((cost, x, y))
    cnt += 1
    tEdge[x].append((y, cost))
    tEdge[y].append((x, cost))
    mst += cost
    T.union(x, y)
for i in range(idx, M):
    oEdge.append(Edge[i])
    

root = 0
P, L, Cs = parorder(tEdge, root)
#C = getcld(P)

Leng = [0]*N
for i in L[1:]:
    p = P[i]
    Leng[i] = 1 + Leng[p]

Dl = [list(range(N))] + [[P[i] for i in range(N)]]
depth = N.bit_length()
for _ in range(depth-1):
    res = [-1]*N
    for i in range(N):
        a = Dl[-1][i]
        if a != root and a != -1:
            res[i] = Dl[-1][a]
    Dl.append(res)

data = [[0]*N] + [[0 if i == root else Cs[i] for i in range(N)]]

for j in range(depth-1):
    res = [0]*N
    for i in range(N):
        a = Dl[j+1][i]
        if a != root and a != -1 and data[-1][a]:
            res[i] = max(data[-1][i], data[-1][a])
    data.append(res)

def query(u0, v0):
    u, v = u0, v0
    if Leng[u] > Leng[v]:
        u, v = v, u
    dif = Leng[v] - Leng[u]
    res = 0
    for i in range(dif.bit_length()):
        if (1<<i) & dif:
            res = max(res, data[i+1][v])
            v = Dl[i+1][v]
    ll = Leng[u].bit_length()
    for i in range(ll):
        k = ll-1-i
        if Dl[k+1][v] != Dl[k+1][u]:
            res = max(res, data[k+1][v], data[k+1][u])
            u = Dl[k+1][u]
            v = Dl[k+1][v]

    if u != v:
        res = max(res, Cs[v], Cs[u])
        
    return res

if mst == X:
    ans = (pow(2, N-1, MOD) - 2) * pow(2, M-(N-1), MOD) % MOD
else:
    ans = 0
cue = 0
ran = 0
dec = 0
for c, u, v in oEdge:
    me = query(u, v)
    if mst + c - me < X:
        dec += 1
    elif mst + c - me == X:
        cue += 1
    else:
        ran += 1

ans = (ans + 2*(pow(2, cue)-1)*pow(2, ran, MOD))%MOD

print(ans)

Submission status: Accepted

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

MOD = 10 ** 9 + 7

N,M = map(int,input().split())
X = int(input())
UVW = [[int(x) for x in input().split()] for _ in range(M)]
UVW.sort(key = lambda x: x[2])

root = list(range(N+1))
def find_root(x):
    y = root[x]
    if x == y:
        return x
    z = find_root(y)
    root[x] = z
    return z

# min spanning tree
tree = [set() for _ in range(N+1)]
min_tree_size = 0
for u,v,w in UVW:
    ru = find_root(u)
    rv = find_root(v)
    if ru == rv:
        continue
    root[ru] = rv
    min_tree_size += w
    tree[u].add((v,w))
    tree[v].add((u,w))

# treeにおける2頂点の間の辺の最大値を求めたい
# LCA。2^n個手前およびそこまでの最大値を覚える

parent = [[0] * 12 for _ in range(N+1)]
max_wt = [[0] * 12 for _ in range(N+1)]
depth = [0] * (N+1)

def dfs(v=1,p=0,dep=0,w=0):
    parent[v][0] = p
    depth[v] = dep
    max_wt[v][0] = w
    for n in range(1,11):
        parent[v][n] = parent[parent[v][n-1]][n-1]
        max_wt[v][n] = max(max_wt[v][n-1], max_wt[parent[v][n-1]][n-1])
    for u,w in tree[v]:
        if u == p:
            continue
        dfs(u,v,dep+1,w)

dfs()

def max_wt_between(x,y):
    # LCA しながら重みの最大値を得る
    wt = 0
    dx,dy = depth[x], depth[y]
    if dx > dy:
        x,y = y,x
        dx,dy = dy,dx
    while dy > dx:
        diff = dy - dx
        step = diff & (-diff)
        n = step.bit_length() - 1
        wt = max(wt, max_wt[y][n])
        y = parent[y][n]
        dy -= step
    if x == y:
        return wt
    step = 1 << 11
    while step:
        n = step.bit_length() - 1
        rx,ry = parent[x][n], parent[y][n]
        if rx != ry:
            wt = max(wt, max_wt[x][n], max_wt[y][n])
            x,y = rx,ry
        step >>= 1
    return max(wt, max_wt[x][0], max_wt[y][0])

# 各edgeに対して、その辺を含む最小の全域木の大きさを求める
min_size = []
for u,v,w in UVW:
    if (v,w) in tree[u]:
        min_size.append(min_tree_size)
    else:
        x = max_wt_between(u,v)
        min_size.append(min_tree_size + w - x)

sm = sum(1 if s < X else 0 for s in min_size)
eq = sum(1 if s == X else 0 for s in min_size)
gr = sum(1 if s > X else 0 for s in min_size)

if eq == 0:
    answer = 0
elif sm == 0:
    # eq 内の辺が完全同色でなければよい
    answer = (pow(2,eq,MOD) - 2) * pow(2,gr,MOD) % MOD
else:
    # sm 内が完全同色でなければならない。
    # eq 内は、smの色と異なる色を持っていれば何でもよい
    answer = 2 * (pow(2,eq,MOD) - 1) * pow(2,gr,MOD) % MOD

print(answer)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
X = int(input())
E = []
C = {}
for i in range(M):
    u, v, w = map(int, input().split())
    E.append((w, u-1, v-1))
    C[w] = C.get(w, 0) + 1
E.sort()

*p, = range(N)
def root(x):
    if x == p[x]:
        return x
    y = p[x] = root(p[x])
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px == py:
        return 0
    if px < py:
        p[py] = px
    else:
        p[px] = py
    return 1

MOD = 10**9 + 7

G0 = [[] for i in range(N)]
K = 0
last = None
U = [0]*M
cost = 0
for i in range(M):
    w, u, v = E[i]
    if unite(u, v):
        cost += w
        U[i] = 1
        if last != w:
            K += C[w]
        G0[u].append((v, w))
        G0[v].append((u, w))
        last = w
def dfs0(u, p, t, cost):
    if u == t:
        return 0
    for v, w in G0[u]:
        if v == p:
            continue
        r = dfs0(v, u, t, cost)
        if r is not None:
            return r | (w == cost)
    return None
def dfs1(u, p, t):
    if u == t:
        return 0
    for v, w in G0[u]:
        if v == p:
            continue
        r = dfs1(v, u, t)
        if r is not None:
            return max(r, w)
    return None

if X - cost < 0:
    print(0)
    exit(0)

K = 0
for i in range(M):
    if U[i]:
        K += 1
        continue
    w, u, v = E[i]
    if dfs0(u, -1, v, w):
        K += 1
        U[i] = 1
if cost == X:
    ans = ((pow(2, K, MOD) - 2)*pow(2, M-K, MOD)) % MOD
    print(ans)
    exit(0)

L = 0
G = 0
for i in range(M):
    w, u, v = E[i]
    if last + (X - cost) < w:
        break
    G += 1
    if U[i]:
        continue
    r = dfs1(u, -1, v) + (X - cost)
    if r == w:
        L += 1
    elif r < w:
        G -= 1

ans = (2*(pow(2, L, MOD)-1)*pow(2, M-G, MOD)) % MOD
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
X = int(input())
E = []
C = {}
for i in range(M):
    u, v, w = map(int, input().split())
    E.append((w, u-1, v-1))
    C[w] = C.get(w, 0) + 1
E.sort()

*p, = range(N)
def root(x):
    if x == p[x]:
        return x
    y = p[x] = root(p[x])
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px == py:
        return 0
    if px < py:
        p[py] = px
    else:
        p[px] = py
    return 1

MOD = 10**9 + 7

G0 = [[] for i in range(N)]
K = 0
last = None
U = [0]*M
cost = 0
for i in range(M):
    w, u, v = E[i]
    if unite(u, v):
        cost += w
        U[i] = 1
        if last != w:
            K += C[w]
        G0[u].append((v, w))
        G0[v].append((u, w))
        last = w
def dfs0(u, p, t, cost):
    if u == t:
        return 0
    for v, w in G0[u]:
        if v == p:
            continue
        r = dfs0(v, u, t, cost)
        if r is not None:
            return r | (w == cost)
    return None
def dfs1(u, p, t):
    if u == t:
        return 0
    for v, w in G0[u]:
        if v == p:
            continue
        r = dfs1(v, u, t)
        if r is not None:
            return max(r, w)
    return None

if X - cost < 0:
    print(0)
    exit(0)

K = 0
for i in range(M):
    if U[i]:
        K += 1
        continue
    w, u, v = E[i]
    if dfs0(u, -1, v, w):
        K += 1
        U[i] = 1
if cost == X:
    ans = ((pow(2, K, MOD) - 2)*pow(2, M-K, MOD)) % MOD
    print(ans)
    exit(0)

L = 0
G = 0
for i in range(M):
    w, u, v = E[i]
    if last + (X - cost) < w:
        break
    G += 1
    if U[i]:
        continue
    r = dfs1(u, -1, v) + (X - cost)
    if r == w:
        L += 1
    elif r < w:
        G -= 1

#print(K, L, M, M-K-L, G)
ans = (2*(pow(2, L, MOD)-1)*pow(2, M-G, MOD)) % MOD
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import minimum_spanning_tree

MOD = 10 ** 9 + 7

N,M = map(int,input().split())
X = int(input())
U,V,W = [],[],[]
for _ in range(M):
    u,v,w = map(int,input().split())
    U.append(u-1)
    V.append(v-1)
    W.append(w)

graph = csr_matrix((W,(U,V)),(N,N))
tree_matrix = minimum_spanning_tree(graph, overwrite = True).astype(int)
min_tree_size = tree_matrix.sum()
tree_matrix = tree_matrix.todense()
tree_matrix += tree_matrix.T

tree = [[] for _ in range(N+10)]
for x,y in zip(*tree_matrix.nonzero()):
    tree[x].append(y)

# treeにおける2頂点の間の辺の最大値を求めたい
# LCA。2^n個手前およびそこまでの最大値を覚える

parent = [[-1] * 12 for _ in range(N+10)]
max_wt = [[0] * 12 for _ in range(N+10)]
depth = [0] * N

def dfs(v=0,p=-1,dep=0):
    parent[v][0] = p
    depth[v] = dep
    if v != 0:
        max_wt[v][0] = tree_matrix[p,v]
    for n in range(1,11):
        parent[v][n] = parent[parent[v][n-1]][n-1]
        max_wt[v][n] = max(max_wt[v][n-1], max_wt[parent[v][n-1]][n-1])
    for w in tree[v]:
        if w == p:
            continue
        dfs(w,v,dep+1)

dfs()

def max_wt_between(x,y):
    # LCA しながら重みの最大値を得る
    wt = 0
    dx,dy = depth[x], depth[y]
    if dx > dy:
        x,y = y,x
        dx,dy = dy,dx
    while dy > dx:
        diff = dy - dx
        step = diff & (-diff)
        n = step.bit_length() - 1
        wt = max(wt, max_wt[y][n])
        y = parent[y][n]
        dy -= step
    if x == y:
        return wt
    step = 1 << 11
    while step:
        n = step.bit_length() - 1
        rx,ry = parent[x][n], parent[y][n]
        if rx != ry:
            x,y = rx,ry
            wt = max(wt, max_wt[x][n], max_wt[y][n])
        step >>= 1
    return max(wt, max_wt[x][0], max_wt[y][0])

# 各edgeに対して、その辺を含む最小の全域木の大きさを求める
min_size = []
for u,v,w in zip(U,V,W):
    if tree_matrix[u,v] != 0:
        min_size.append(min_tree_size)
    else:
        x = max_wt_between(u,v)
        min_size.append(min_tree_size + w - x)

sm = sum(1 if s < X else 0 for s in min_size)
eq = sum(1 if s == X else 0 for s in min_size)
gr = sum(1 if s > X else 0 for s in min_size)

if eq == 0:
    answer = 0
elif sm == 0:
    # eq 内の辺が完全同色でなければよい
    answer = (pow(2,eq,MOD) - 2) * pow(2,gr,MOD) % MOD
else:
    # sm 内が完全同色でなければならない。
    # eq 内は、smの色と異なる色を持っていれば何でもよい
    answer = 2 * (pow(2,eq,MOD) - 1) * pow(2,gr,MOD) % MOD

print(answer)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import minimum_spanning_tree

MOD = 10 ** 9 + 7

N,M = map(int,input().split())
X = int(input())
U,V,W = [],[],[]
for _ in range(M):
    u,v,w = map(int,input().split())
    U.append(u-1)
    V.append(v-1)
    W.append(w)

graph = csr_matrix((W,(U,V)),(N,N))
tree_matrix = minimum_spanning_tree(graph, overwrite = True).astype(int)
min_tree_size = tree_matrix.sum()
tree_matrix += tree_matrix.T

tree = [[] for _ in range(N+10)]
for x,y in zip(*tree_matrix.nonzero()):
    tree[x].append(y)

# treeにおける2頂点の間の辺の最大値を求めたい
# LCA。2^n個手前およびそこまでの最大値を覚える

parent = [[-1] * 12 for _ in range(N+10)]
max_wt = [[0] * 12 for _ in range(N+10)]
depth = [0] * N

tree_matrix = tree_matrix.todense()

def dfs(v=0,p=-1,dep=0):
    parent[v][0] = p
    depth[v] = dep
    if v != 0:
        max_wt[v][0] = tree_matrix[p,v]
    for n in range(1,11):
        parent[v][n] = parent[parent[v][n-1]][n-1]
        max_wt[v][n] = max(max_wt[v][n-1], max_wt[parent[v][n-1]][n-1])
    for w in tree[v]:
        if w == p:
            continue
        dfs(w,v,dep+1)

dfs()

def max_wt_between(x,y):
    # LCA しながら重みの最大値を得る
    wt = 0
    dx,dy = depth[x], depth[y]
    if dx > dy:
        x,y = y,x
        dx,dy = dy,dx
    while dy > dx:
        diff = dy - dx
        step = diff & (-diff)
        n = step.bit_length() - 1
        wt = max(wt, max_wt[y][n])
        y = parent[y][n]
        dy -= step
    if x == y:
        return wt
    step = 1 << 11
    while step:
        n = step.bit_length() - 1
        rx,ry = parent[x][n], parent[y][n]
        if rx != ry:
            x,y = rx,ry
            wt = max(wt, max_wt[x][n], max_wt[y][n])
        step >>= 1
    return max(wt, max_wt[x][0], max_wt[y][0])

# 各edgeに対して、その辺を含む最小の全域木の大きさを求める
min_size = []
for u,v,w in zip(U,V,W):
    if tree_matrix[u,v] != 0:
        min_size.append(min_tree_size)
    else:
        x = max_wt_between(u,v)
        min_size.append(min_tree_size + w - x)

sm = sum(1 if s < X else 0 for s in min_size)
eq = sum(1 if s == X else 0 for s in min_size)
gr = sum(1 if s > X else 0 for s in min_size)

if eq == 0:
    answer = 0
elif sm == 0:
    # eq 内の辺が完全同色でなければよい
    answer = (pow(2,eq,MOD) - 2) * pow(2,gr,MOD) % MOD
else:
    # sm 内が完全同色でなければならない。
    # eq 内は、smの色と異なる色を持っていれば何でもよい
    answer = 2 * (pow(2,eq,MOD) - 1) * pow(2,gr,MOD) % MOD

print(answer)