MST의 기댓값

시간 제한1초메모리 제한512 MB

요약
가중치가 있는 연결 그래프에 모든 정점 쌍과 0 이상 10^9 이하의 가중치로 이루어진 삼중항 중 하나를 무작위로 골라 간선을 추가할 때, Minimum Spanning Tree 가중치 합의 기댓값을 10^9+7로 나눈 나머지를 구한다.
난이도

어려움10점 중 9점

유형
최소 신장 트리, 유니온 파인드, 수학, 조합론
정답자
아직 제출이 없습니다

문제

정점 NN개, 간선 MM개의 무향 가중치 연결 그래프 GG가 입력된다.

집합 SS는 (1≤i<j≤N;0≤w≤109)(1 \leq i < j \leq N; 0 \leq w \leq 10^9)를 만족하는 모든 정수 i,j,wi, j, w에 대해 (i,j,w)(i,j,w)를 원소로 가지고 있다.

집합 SS에서 한 원소 (i,j,w)(i,j,w)를 무작위로 골라 GG에 정점 ii와 jj를 연결하는 가중치 ww의 간선을 추가로 연결한 그래프 G′G^{\prime}를 만들었을 때 G′G^{\prime}의 MST(Minimum Spanning Tree)의 가중치의 합의 기댓값을 구하여라.

입력

첫째 줄에 NN과 MM이 주어진다. (2≤N≤100,000;N−1≤M≤200,000)(2 \leq N \leq 100\\,000; N-1 \leq M \leq 200\\,000)

그 다음 MM개 줄에 정점 uu와 vv를 가중치 cc로 연결하는 간선을 의미하는 간선정보 u,v,cu, v, c가 주어진다. (1≤u,v≤N;u≠v;0≤c≤109)(1 \leq u,v \leq N; u \neq v;0 \leq c \leq 10^9)

출력

첫째 줄에 무작위로 간선을 추가했을 때 MST의 가중치 합의 기댓값을 109+710^9+7으로 나눈 나머지를 출력한다.

힌트

그래프의 모든 정점들을 포함하는 연결된 부분 그래프 중에서 간선의 가중치의 합이 최소인 것을 MST(Minimum Spanning Tree)라고 한다.

기약분수 yx\frac{y}{x}에 대해 xx가 소수 pp의 배수가 아니라면, xz≡y(modp)xz \equiv y \pmod{p}를 만족하는 0≤z<p0 \leq z < p인 정수 zz가 정확히 하나 존재하며, zz는 yx\frac{y}{x}를 pp로 나눈 나머지를 나타낸다.

예제1

  1. 예제 1

    입력
    3 3
1 2 1
2 3 4
3 1 2
    예상 출력
    388888895