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: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    def get_group(k):
        g = pd[k]
        if g < 0:
            return k
        gg = get_group(g)
        pd[k] = gg
        return gg

    def merge(j, k):
        g1 = get_group(j)
        g2 = get_group(k)
        if g1 != g2:
            d1 = -pd[g1]
            d2 = -pd[g2]
            if d2 > d1:
                g1, g2 = g2, g1
            pd[g2] = g1
            if d1 == d2:
                pd[g1] -= 1

    n, m = map(int, input().split())
    x = int(input())
    ee = []
    for _ in range(m):
        u, v, w = map(int, input().split())
        ee.append((w, u - 1, v - 1))
    ee.sort()
    # print(ee)

    # union find 準備
    n_nodes = n - 1
    pd = [-1] * (n_nodes + 1)
    # 無条件の最小全域木を作る
    dd = [-1] * m
    s = 0
    for i in range(m):
        w, u, v = ee[i]
        if get_group(u) == get_group(v): continue
        s += w
        merge(u, v)
        dd[i] = 0
    # 最小サイズがxを超えていたら終わり
    if s > x:
        print(0)
        exit()
    # 使った辺に最小サイズを記録
    for i in range(m):
        if dd[i] == 0: dd[i] = s
    # 使っていない辺を1つずつ試して、サイズを記録
    for si in range(m):
        if dd[si] != -1: continue
        pd = [-1] * (n_nodes + 1)
        w, u, v = ee[si]
        dd[si] = 0
        merge(u, v)
        s = w
        for i in range(m):
            w, u, v = ee[i]
            if get_group(u) == get_group(v): continue
            s += w
            merge(u, v)
            if dd[i] == -1:
                dd[i] = 0
        for i in range(m):
            if dd[i] == 0: dd[i] = s
    # print(dd)
    c_s = 0  # count small サイズがx未満の辺の数
    c_x = 0  # count x サイズがxの辺の数
    for d in dd:
        if d < x: c_s += 1
        if d == x: c_x += 1
    # print(c_s,c_x)
    if c_s == 0:
        print(pow(2, m) - pow(2, m - c_s - c_x + 1))
    else:
        print(pow(2, m - c_s + 1) - pow(2, m - c_s - c_x + 1))

main()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    def get_group(k):
        g = pd[k]
        if g < 0:
            return k
        gg = get_group(g)
        pd[k] = gg
        return gg

    def merge(j, k):
        g1 = get_group(j)
        g2 = get_group(k)
        if g1 != g2:
            d1 = -pd[g1]
            d2 = -pd[g2]
            if d2 > d1:
                g1, g2 = g2, g1
            pd[g2] = g1
            if d1 == d2:
                pd[g1] -= 1

    n, m = map(int, input().split())
    x = int(input())
    ee = []
    for _ in range(m):
        u, v, w = map(int, input().split())
        ee.append((w, u - 1, v - 1))
    ee.sort()
    # print(ee)

    # union find 準備
    n_nodes = n - 1
    pd = [-1] * (n_nodes + 1)
    # 無条件の最小全域木を作る
    dd = [-1] * m
    s = 0
    for i in range(m):
        w, u, v = ee[i]
        if get_group(u) == get_group(v): continue
        s += w
        merge(u, v)
        dd[i] = 1
    # 最小サイズがxを超えていたら終わり
    if s > x:
        print(0)
        exit()
    # 使った辺に最小サイズを記録
    for i in range(m):
        if dd[i] == 1: dd[i] = s
    # 使っていない辺を1つずつ試して、サイズを記録
    for si in range(m):
        if dd[si] != -1: continue
        pd = [-1] * (n_nodes + 1)
        w, u, v = ee[si]
        merge(u, v)
        s = w
        for i in range(m):
            w, u, v = ee[i]
            if get_group(u) == get_group(v): continue
            s += w
            merge(u, v)
        dd[si] = s
    #print(dd)
    c_s = 0  # count small サイズがx未満の辺の数
    c_x = 0  # count x サイズがxの辺の数
    for d in dd:
        if d < x: c_s += 1
        if d == x: c_x += 1
    #print(c_s,c_x)
    if c_s==0:
        print(pow(2, m)- pow(2, m - c_s - c_x + 1))
    else:
        print(pow(2, m - c_s + 1) - pow(2, m - c_s - c_x + 1))

main()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    def get_group(k):
        g = pd[k]
        if g < 0:
            return k
        gg = get_group(g)
        pd[k] = gg
        return gg

    def merge(j, k):
        g1 = get_group(j)
        g2 = get_group(k)
        if g1 != g2:
            d1 = -pd[g1]
            d2 = -pd[g2]
            if d2 > d1:
                g1, g2 = g2, g1
            pd[g2] = g1
            if d1 == d2:
                pd[g1] -= 1

    n, m = map(int, input().split())
    x = int(input())
    ee = []
    for _ in range(m):
        u, v, w = map(int, input().split())
        ee.append((w, u - 1, v - 1))
    ee.sort()
    # print(ee)

    # union find 準備
    n_nodes = n - 1
    pd = [-1] * (n_nodes + 1)
    # 無条件の最小全域木を作る
    dd = [-1] * m
    s = 0
    for i in range(m):
        w, u, v = ee[i]
        if get_group(u) == get_group(v): continue
        s += w
        merge(u, v)
        dd[i] = 1
    # 最小サイズがxを超えていたら終わり
    if s > x:
        print(0)
        exit()
    # 使った辺に最小サイズを記録
    for i in range(m):
        if dd[i] == 1: dd[i] = s
    # 使っていない辺を1つずつ試して、サイズを記録
    for si in range(m):
        if dd[si] != -1: continue
        pd = [-1] * (n_nodes + 1)
        w, u, v = ee[si]
        merge(u, v)
        s = w
        for i in range(m):
            w, u, v = ee[i]
            if get_group(u) == get_group(v): continue
            s += w
            merge(u, v)
        dd[si] = s
    #print(dd)
    c_s = 0  # count small サイズがx未満の辺の数
    c_x = 0  # count x サイズがxの辺の数
    for d in dd:
        if d < x: c_s += 1
        if d == x: c_x += 1
    #print(c_s,c_x)
    if c_s==0:
        print(pow(2, m)-2)
    else:
        print(pow(2, m - c_s + 1) - pow(2, m - c_s - c_x + 1))

main()

Submission status: Wrong Answer

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:
            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 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: Wrong Answer

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

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 = np.array(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: Wrong Answer

Solution code:
# E
import numpy as np

N, M = map(int, input().split())
X = int(input())
U_list = []
V_list = []
W_list = []

for _ in range(M):
    u, v, w = map(int, input().split())
    U_list.append(u)
    V_list.append(v)
    W_list.append(w)

ind_vec = np.arange(N+1)

def find_parent(k):
    l = ind_vec[k]
    search_list = []
    while l != k:
        search_list.append(k)
        k = l
        l = ind_vec[k]
    return k, search_list

w_arr = np.array(W_list)
w_arg = np.argsort(w_arr)

min_weight = 0
max_weight = 0

for m in range(M):
    i = w_arg[m]
    u = U_list[i]
    v = V_list[i]
    
    up, ul = find_parent(u)
    for j in ul:
        ind_vec[j] = up
    
    vp, vl = find_parent(v)
    for j in vl:
        ind_vec[j] = vp
    
    if up != vp:
        min_weight += W_list[i]
        ind_vec[vp] = up
        max_weight = W_list[i]
        
# min = W
cnt_small = 0
for i in range(M):
    if W_list[i] <= max_weight:
        cnt_small += 1
        
if min_weight == X:
    print((pow(2, cnt_small, 10**9+7) - 2) * pow(2, M - cnt_small, 10**9+7) % (10**9+7))
elif min_weight > X:
    print(0)
else:
    print(pow(2, M - cnt_small, 10**9+7))

Submission status: Wrong Answer

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
    if dfs1(u, -1, v) + (X - cost) == w:
        L += 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: Wrong Answer

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

K = 0
last = None
cost = 0
for w, u, v in E:
    if unite(u, v):
        cost += w
        if last != w:
            K += C[w]
        last = w
if X == cost:
    ans = ((pow(2, K, MOD) - 2)*pow(2, M-K, MOD)) % MOD
    print(ans)
    exit(0)
trg = last + (X - cost)
if X - cost < 0 or C.get(trg, 0) == 0:
    print(0)
    exit(0)
L = 0
for w, u, v in E:
    if trg <= w:
        break
    L += 1
ans = (2*(pow(2, C[trg], MOD) - 1)*pow(2, M - C[trg] - L, MOD)) % MOD
print(ans)

Submission status: Wrong Answer

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

K = 0
last = None
cost = 0
for w, u, v in E:
    if unite(u, v):
        cost += w
        if last != w:
            K += C[w]
        last = w
if X == cost:
    ans = ((pow(2, K, MOD) - 2)*pow(2, M-K, MOD)) % MOD
    print(ans)
    exit(0)
trg = last + (X - cost)
if C.get(trg, 0) == 0:
    print(0)
    exit(0)
L = 0
for w, u, v in E:
    if trg <= w:
        break
    L += 1
ans = (2*(pow(2, C[trg], MOD) - 1)*pow(2, M - C[trg] - L, MOD)) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    def __init__(self, N):
        self.par = list(range(N))
        self.size = [1] * N

    def root(self, v):
        if v == self.par[v]:
            return v
        self.par[v] = self.root(self.par[v])
        return self.par[v]

    def unite(self, u, v):
        u = self.root(u)
        v = self.root(v)
        if u == v:
            return
        if self.size[u] < self.size[v]:
            u, v = v, u
        self.par[v] = u
        self.size[u] += self.size[v]

    def same(self, u, v):
        return self.root(u) == self.root(v)

    def num(self, u):
        return self.size[self.root(u)]

def kruskal(k):
    w, u, v = E[k]
    res = w
    uf = UnionFind(N)
    uf.unite(u, v)
    for z, x, y in E:
        if uf.same(x, y):
            continue
        res += z
        uf.unite(x, y)
        if uf.num(x) == N:
            break
    return res

mod = 10 ** 9 + 7
N, M = map(int, input().split())
X = int(input())
E = [tuple()] * M
for i in range(M):
    u, v, w = map(int, input().split())
    E[i] = (w, u-1, v-1)
E = sorted(E)
ans = 0
z = 2
for i in range(M-1, 0, -1):
    s = kruskal(i)
    if s >= X:
        if s > X:
            ans *= 2
            ans %= mod
        else:
            ans += z
            ans %= mod
        z *= 2
        z %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import *

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    md = 10 ** 9 + 7

    def get_group(k):
        g = pd[k]
        if g < 0:
            return k
        gg = get_group(g)
        pd[k] = gg
        return gg

    def merge(j, k):
        g1 = get_group(j)
        g2 = get_group(k)
        if g1 != g2:
            d1 = -pd[g1]
            d2 = -pd[g2]
            if d2 > d1:
                g1, g2 = g2, g1
            pd[g2] = g1
            if d1 == d2:
                pd[g1] -= 1

    n, m = map(int, input().split())
    x = int(input())
    ee = []
    for _ in range(m):
        u, v, w = map(int, input().split())
        ee.append((w, u - 1, v - 1))
    ee.sort()
    # print(ee)

    # union find 準備
    n_nodes = n - 1
    pd = [-1] * (n_nodes + 1)
    # 無条件の最小全域木を作る
    dd = [-1] * m
    s = 0
    for i in range(m):
        w, u, v = ee[i]
        if get_group(u) == get_group(v): continue
        s += w
        merge(u, v)
        dd[i] = 0
    # 最小サイズがxを超えていたら終わり
    if s > x:
        print(0)
        exit()
    # 使った辺に最小サイズを記録
    for i in range(m):
        if dd[i] == 0: dd[i] = s
    # 使っていない辺を1つずつ試して、サイズを記録
    for si in range(m):
        if dd[si] != -1: continue
        pd = [-1] * (n_nodes + 1)
        w, u, v = ee[si]
        dd[si] = 0
        merge(u, v)
        s = w
        for i in range(m):
            w, u, v = ee[i]
            if get_group(u) == get_group(v): continue
            s += w
            merge(u, v)
            if dd[i] == -1:
                dd[i] = 0
        for i in range(m):
            if dd[i] == 0: dd[i] = s
    dd.sort()

    # print(dd)
    # print(xi, x1i)
    def cnt(k):
        idx = bisect_right(dd, k)
        res = pow(2, m - idx + 1, md) - 2
        if idx == 0:
            res = pow(2, m, md) - 2
        return res

    print((cnt(x - 1) - cnt(x)) % md)

main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import array
import heapq


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

    def find(self, x):
        while 0 <= self.table[x]:
            x = self.table[x]
        return x

    def unite(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            dx = -self.table[rx]
            dy = -self.table[ry]
            if dx != dy:
                if dx < dy:
                    self.table[rx] = ry
                else:
                    self.table[ry] = rx
            else:
                self.table[rx] -= 1
                self.table[ry] = rx
        return


M = 10 ** 9 + 7
INF = 2 ** 31 - 1


def prim(n, adj_list, e):
    pred = [-1] * n
    weights = [INF] * n

    w1, u0, u1 = e

    weights[u0] = 0
    pred[u1] = u0
    weights[u1] = 0

    pq = [(weights[v], v) for v in range(n)]
    heapq.heapify(pq)

    in_pq = array.array('B', (True for _ in range(n)))
    in_pq[u0] = in_pq[u1] = False
    for u in [u0, u1]:
        for v, w in adj_list[u]:
            if in_pq[v]:
                if w < weights[v]:
                    pred[v] = u
                    weights[v] = w
                    heapq.heappush(pq, (w, v))
                    in_pq[v] = True

    while pq:
        _, u = heapq.heappop(pq)
        in_pq[u] = False
        for v, w in adj_list[u]:
            if in_pq[v]:
                if w < weights[v]:
                    pred[v] = u
                    weights[v] = w
                    heapq.heappush(pq, (w, v))
                    in_pq[v] = True

    return sum(weights) + w1


def solve(n, m, x, edges, adj_list):
#    uf = UnionFind(m)
#    used = array.array('B', (False for _ in range(m)))

#    edges.sort()

    s = 0
    t = 0
    for (i, e) in enumerate(edges):
        y = prim(n, adj_list, e)
        if y < x:
            s += 1
        elif y == x:
            t += 1


    pow2 = array.array('I', (0 for _ in range(m + 1)))

    if t == 0:
        return 0
    else:
        r = 1
        for i in range(max(t, m - s - t + 1) + 1):
            pow2[i] = r
            r *= 2
            r %= M
        if s == 0:
            ans = (pow2[t] - 2) * pow2[m - t]
        else:
            ans = (pow2[t] - 1) * pow2[m - s - t + 1]
        return ans % M


def main():
    n, m = input().split()
    n = int(n)
    m = int(m)
    x = input()
    x = int(x)
    edges = []
    adj_list = [[] for _ in range(n)]
    for _ in range(m):
        u, v, w = input().split()
        u = int(u) - 1
        v = int(v) - 1
        w = int(w)
        edges.append((w, u, v))
        adj_list[u].append((v, w))
        adj_list[v].append((u, w))


    print(solve(n, m, x, edges, adj_list))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

"""

https://atcoder.jp/contests/arc093/tasks/arc093_c

各辺を含む最小全域木を考える
→重みがX未満なら、その全域木に含まれる辺は全て同一色で塗る必要がある

全ての辺に対してやれば十分？
→ではない

むしろ、X未満の全域木となった辺すべて同一色で塗る必要がある？
辺A,Bを含む全域偽は重みがX未満だが、同一色で塗る必要がないとする
→AとBの最小全域木は共有辺を一切持たない
A,Bを二つの頂点集合に分ける。頂点集合間は、別の辺l,Lで結ばれている
元の辺を除いた重みの輪を a,bとすると、 a+l < X  b+L < X である
よって、辺を交換するとどちらかは必ずX未満となる
→よって、その辺を含む最小全域木

AとBの辺を少なくとも1つづつ含む最小全域木が存在することを示せばいい
最小の重みの辺LがAにあるとする
Lに接続されている頂点Xには、Bの辺が1本ささっている
この辺を含む最小全域木をクラスカル法で構築していくと、Aの最小の辺を絶対含む
→よって、ただしい

まず、各辺を含む最小全域木を考え、重みがX未満なら白で塗る
重みがXを超える場合、重みXの全域木に含まれることはないため好きな色で塗る
→不要なため以後グラフに無いものとして扱う

今グラフには白い辺(X未満)と、未定(X)の辺がある
塗分け方は 2^X である。ここから補集合(Xの全域木を構成できない場合)を引く
全部白の場合は自明に無理

白で塗られた辺が1つ以上存在する場合を考える
黒が1つでも入っていれば構成可能？
→最小全域木に必ず白を含むことを証明できれば良い
未定の辺の最小 >= 白い辺の最小 が示せれば、白い辺の片方の頂点に来た時に絶対選ばれるのでおｋ
未定の辺が最小だった場合、片方に来た時に選ばれてしまうので示された

入っていない場合、すべて同一色でなければ構成可能？
→これも同様に証明可能なはず

"""

from sys import stdin
import sys

def uf_find(n,p):

    ufl = []

    while p[n] != n:
        ufl.append(n)
        n = p[n]

    for i in ufl:
        p[i] = n

    return n


def uf_union(a,b,p,rank):

    ap = uf_find(a,p)
    bp = uf_find(b,p)

    if ap == bp:
        return False
    else:

        if rank[ap] > rank[bp]:
            p[bp] = ap
        elif rank[ap] < rank[bp]:
            p[ap] = bp
        else:
            p[bp] = ap
            rank[ap] += 1

        return True

N,M = map(int,stdin.readline().split())

X = int(stdin.readline())

wvu = []

for i in range(M):

    u,v,w = map(int,stdin.readline().split())
    wvu.append((w,v-1,u-1))

overX = 0
justX = 0
underX = 0
wvu.sort()

for i in range(M):

    p = [i for i in range(N)]
    rank = [0] * N
    h = 0

    h += wvu[i][0]
    uf_union(wvu[i][1],wvu[i][2],p,rank)

    for j in range(M):

        if uf_union(wvu[j][1],wvu[j][2],p,rank):
            h += wvu[j][0]

    if h > X:
        overX += 1
    elif h == X:
        justX += 1
    else:
        underX += 1

print (overX,justX,underX,file=sys.stderr)
ans = 0
mod = 10**9+7

if justX == 0:
    ans = 0
elif underX > 0:
    ans = 2 * pow(2,overX,mod) * (pow(2,justX,mod)-1)
else:
    ans = pow(2,overX,mod) * (pow(2,justX,mod)-2)

print (ans % mod)

Submission status: Accepted

Solution code:
class UnionFindVerSize():
    def __init__(self, N):
        self._parent = [n for n in range(0, N)]
        self._size = [1] * N

    def find_root(self, x):
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x])
        return self._parent[x]

    def unite(self, x, y):
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans

import sys

input=sys.stdin.buffer.readline

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

Edge.sort()
base=0
edge=[[] for i in range(N)]
uf=UnionFindVerSize(N)
for c,a,b in Edge:
    if not uf.is_same_group(a,b):
        uf.unite(a,b)
        base+=c
        edge[a].append((b,c))
        edge[b].append((a,c))

weight=[0]*N
depth=[0]*N
parent=[0]*N
rmq=[0]*N
def wdfs(v,pv):
    for nv,cost in edge[v]:
        if nv!=pv:
            parent[nv]=v
            depth[nv]=depth[v]+1
            weight[nv]=cost
            rmq[nv]=max(weight[nv],weight[v])
            wdfs(nv,v)

wdfs(0,-1)

LV = (N-1).bit_length()
def construct(prv):
    kprv = [prv]
    S = prv
    for k in range(LV):
        T = [0]*N
        for i in range(N):
            if S[i] is None:
                continue
            T[i] = S[S[i]]
        kprv.append(T)
        S = T
    return kprv

kprv=construct(parent)

def constructkrmq(r):
    krmq=[r]
    S=r
    for k in range(LV):
        T=[0]*N
        for i in range(N):
            if S[i] is None:
                continue
            T[i]=max(S[i],S[kprv[k][i]])
        krmq.append(T)
        S=T
    return krmq


krmq=constructkrmq(rmq)

def lca(u, v):
    dd = depth[v] - depth[u]
    if dd < 0:
        u, v = v, u
        dd = -dd

    # assert depth[u] <= depth[v]
    for k in range(LV+1):
        if dd & 1:
            v = kprv[k][v]
        dd >>= 1

    # assert depth[u] == depth[v]
    if u == v:
        return u

    for k in range(LV-1, -1, -1):
        pu = kprv[k][u]; pv = kprv[k][v]
        if pu != pv:
            u = pu; v = pv

    # assert kprv[0][u] == kprv[0][v]
    return kprv[0][u]

def RMQ(u,v):
    #assert depth[u]>depth[v]
    if depth[u]==depth[v]:
        return 0

    num=depth[u]-depth[v]-1
    pos=u
    res=weight[u]
    for i in range(LV-1,-1,-1):
        if num>>i &1==1:
            res=max(res,krmq[i][pos])
            pos=kprv[i][pos]
    return res


up=0
down=0
same=0
for c,u,v in EEdge:
    LCA=lca(u,v)
    minus=max(RMQ(u,LCA),RMQ(v,LCA))
    if base-minus+c>X:
        up+=1
    elif base-minus+c<X:
        down+=1
    else:
        same+=1

if down==0:
    if same==0:
        print(0)
    else:
        ans=pow(2,M,mod)-2*pow(2,up,mod)
        print(ans%mod)
else:
    ans=2*(pow(2,same,mod)-1)*pow(2,up,mod)
    print(ans%mod)

Submission status: Accepted

Solution code:
import sys
mod = 10 ** 9 + 7
sys.setrecursionlimit(mod)
input = sys.stdin.readline

def root(v):
    if v == par[v]:
        return v
    par[v] = root(par[v])
    return par[v]

def unite(u, v):
    u = root(u)
    v = root(v)
    if u == v:
        return
    if rank[u] < rank[v]:
        u, v = v, u
    par[v] = u
    if rank[u] == rank[v]:
        rank[u] += 1

def same(u, v):
    return root(u) == root(v)

def kruskal(edges):
    tree = [[] for _ in range(N)]
    used = [False] * M
    weight = 0
    for i, (w, u, v) in enumerate(edges):
        if same(u, v):
            continue
        unite(u, v)
        weight += w
        tree[u].append((w, v))
        tree[v].append((w, u))
        used[i] = True
    return weight, tree, used

def dfs(v=0, p=-1, d=0, w=0):
    parent[0][v] = p
    depth[v] = d
    max_w[0][v] = w
    for w, u in T[v]:
        if u == p:
            continue
        dfs(u, v, d+1, w)

def lca(u, v):
    if depth[u] > depth[v]:
        u, v = v, u
    tmp = 0
    while depth[v] > depth[u]:
        diff = depth[v] - depth[u]
        k = diff.bit_length() - 1
        tmp = max(tmp, max_w[k][v])
        v = parent[k][v]
    if u == v:
        return tmp
    for k in range(logN-1, -1, -1):
        if parent[k][u] != parent[k][v]:
            tmp = max(tmp, max_w[k][u], max_w[k][v])
            u = parent[k][u]
            v = parent[k][v]
    return max(tmp, max_w[0][u], max_w[0][v])

def modpow(x, p):
    if p == 0:
        return 1
    elif p == 1:
        return x % mod
    if p % 2 == 1:
        return x * modpow(x, p-1) % mod
    return modpow(x * x % mod, p // 2) % mod

N, M = map(int, input().split())
logN = (N - 1).bit_length()
X = int(input())
E = [tuple()] * M
for i in range(M):
    u, v, w = map(int, input().split())
    E[i] = (w, u-1, v-1)
E = sorted(E, key=lambda x: x[0])
par = list(range(N))
rank = [1] * N
W, T, F = kruskal(E)
depth = [0] * N
parent = [[0] * N for _ in range(logN+1)]
max_w = [[0] * N for _ in range(logN+1)]
dfs()
for k in range(logN):
    for v in range(N):
        if parent[k][v] < 0:
            parent[k+1][v] = -1
            max_w[k+1][v] = max_w[k][v]
        else:
            parent[k+1][v] = parent[k][parent[k][v]]
            max_w[k+1][v] = max(max_w[k][v], max_w[k][parent[k][v]])

le = 0
eq = 0
ge = 0
for i, (w, u, v) in enumerate(E):
    s = W
    if not F[i]:
        s += (w - lca(u, v))
    if s < X:
        le += 1
    else:
        if s == X:
            eq += 1
        else:
            ge += 1
ans = 0
if eq != 0:
    if le == 0:
        ans = (modpow(2, eq) - 2) * modpow(2, ge) % mod
    else:
        ans = 2 * (modpow(2, eq) - 1) * modpow(2, ge) % mod
print(ans)