최소스패닝트리 문제중에 단순한 최소 스패닝트리 말고

각 간선을 포함하는 최소 스패닝트리나 포함하지 않는 최소 스패닝트리를 각 간선마다 비용을 모두 구하는 문제는 어떻게 풀어야 하나요...?

각 간선을 포함or배제시키고 스패닝 트리를 구하게 하면 N^2logN이 나오는데

당연히 N^2logN은 아니고 NlogN으로 나올거같은데...

문제 풀다보니까 이런거 비슷한게 많이 나오는데 할줄을 몰라서요 ㅠㅠㅠ

아니면 스패닝트리 관련된 사이트좀 알려주시면 감사하겠습니다 ㅠㅠ