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
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 struct_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))
            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):
    # 最小全域木が白黒含むならXはその重さでないといけない
    # そうでないなら、最小全域木以外の辺を使えるのはせいぜい1本まで→各辺の増加分を見る

    adopted_weight, spanning_links, not_spanning_links = struct_spanning_tree(n, uvw)
    # print(adopted_weight)
    # print(spanning_links)
    # print(not_spanning_links)
    if x < adopted_weight:
        return 0
    diff = x - adopted_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
    replace_exact_cost = 2 * (pow(2, exact_count, MOD) - 1) * pow(2, upper_count, MOD) % MOD
    if diff > 0:
        return replace_exact_cost

    use_first_spanning = (pow(2, n - 1, MOD) - 2) * pow(2, m - n + 1, MOD) % MOD
    return (use_first_spanning + replace_exact_cost) % 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: Wrong Answer

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:
                tu = mu
                tv = mv
                max_path = max(max_path, self.max_paths[k][tu], self.max_paths[k][tv])
        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 struct_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))
            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):
    # 最小全域木が白黒含むならXはその重さでないといけない
    # そうでないなら、最小全域木以外の辺を使えるのはせいぜい1本まで→各辺の増加分を見る

    adopted_weight, spanning_links, not_spanning_links = struct_spanning_tree(n, uvw)
    # print(adopted_weight)
    # print(spanning_links)
    # print(not_spanning_links)
    if x < adopted_weight:
        return 0
    diff = x - adopted_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
    replace_exact_cost = 2 * (pow(2, exact_count, MOD) - 1) * pow(2, upper_count, MOD) % MOD
    if diff > 0:
        return replace_exact_cost

    use_first_spanning = (pow(2, n - 1, MOD) - 2) * pow(2, m - n + 1, MOD) % MOD
    return (use_first_spanning + replace_exact_cost) % 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: Wrong Answer

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

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()
    cnt = -1
    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]
        else:
            cnt = k
    if u != v:
        res = max(res, data[cnt+1][v], data[cnt+1][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: Wrong Answer

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])
    


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

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

inf = 1<<31
Dl = [list(range(N))] + [[P[i] for i in range(N)]]
depth = N.bit_length()
root = 0
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:
            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()
    cnt = -1
    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]
        else:
            cnt = k
    if u != v:
        res = max(res, data[cnt+1][v], data[cnt+1][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: Wrong Answer

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])
    


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

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

inf = 1<<31
Dl = [list(range(N))] + [[P[i] for i in range(N)]]
depth = N.bit_length()
root = 0
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:
            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()
    cnt = -1
    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]
        else:
            cnt = k
    res = max(res, data[cnt+1][v], data[cnt+1][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: 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

    md = 10 ** 9 + 7
    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つずつ試して、サイズを記録
    xi = 0 if s == x else m
    x1i = m
    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
        if xi == m and s == x:
            xi = si
        if s > x:
            x1i = si
            break
    # print(dd)
    # print(xi, x1i)
    if xi == 0:
        print((pow(2, m, md) - pow(2, m - x1i + 1, md)) % md)
    else:
        print((pow(2, m - xi + 1, md) - pow(2, m - x1i + 1, md)) % md)

main()

Submission status: Wrong Answer

Solution code:
import sys
from bisect import *

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
    dd.sort()
    #print(dd)
    #print(xi, x1i)
    def cnt(k):
        idx=bisect_right(dd,k)
        res=pow(2,m-idx+1)-2
        if idx==0:
            res=pow(2,m)-2
        return res
    print(cnt(x-1)-cnt(x))
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] = 0
    # 最小サイズがxを超えていたら終わり
    if s > x:
        print(0)
        exit()
    # 使った辺に最小サイズを記録
    for i in range(m):
        if dd[i] == 0: dd[i] = s
    # 使っていない辺を1つずつ試して、サイズを記録
    xi = 0 if s == x else m
    x1i = m
    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
        if xi == m and s == x:
            xi = si
        if s > x:
            x1i = si
            break
    #print(dd)
    #print(xi, x1i)
    if xi == 0:
        print(pow(2, m) - pow(2, m - x1i + 1))
    else:
        print(pow(2, m - xi + 1) - pow(2, m - x1i + 1))

main()