You are not logged in. Please login at to post your questions!


SPANTREE - Editorial



Authors: Sidhant Bansal
Testers: Jingbo Shang, Istvan Nagy
Editorialist: Vaibhav Tulsyan


Given that there exists an undirected weighted connected graph with $N$ vertices, find the total weight of its Minimum Spanning Tree.

You can perform 2 kinds of queries:

  1. Provide 2 non-empty, non-intersectin sets of vertices $A$ and $B$ as input to the judge and get the minimum weighted edge between any pair of nodes $u \subseteq A$ and $v \subseteq B$. If there is no such edge, the judge returns -1.
  2. Send the weight of the MST to the judge.

The cost of performing a query is $|A|$. The max cost that can be incurred is $10^4$.


$2 \le N \le 1000$

$1 \le weight_{edge} \le 10^5$


Will Kruskal's/Prim's Algorithm work?

Primitive Kruskal / Prim will not work. Kruskal's wont work because we will perform $N^2$ queries - once for each pair of nodes, where the cost for each query will be $1$.

For Prim's the set of nodes you know the answer for, will keep on increasing. Hence, the cost for the queries would be something like: $1, 2, 3, ... , N/2, N/2, (N/2 - 1), ..., 3, 2, 1$. Hence, the cost would be of the order $O(N^2)$.


  1. Find the nearest node of each node $u$ by using a query of the format: $[u]$ vs. all except $u$.

    • This gives us connected components of size $2$.
  2. In increasing order of component size, we can continue to perform queries like: [component] vs. [all except component].

You can observe that after every query, the component's size gets doubled.

Since the size of a component always gets doubled, we can say that every vertex occurs as a vertex in $A$ at most $log(N)$ times. Components can be maintained using a DSU.

Each vertex contributes $1$ to the net cost. Hence, the overall cost is bounded by $O(N * log(N))$.

Since the value of $N$ is at most $1000$, our bound ensures that the max cost of $10^4$ is never exceeded.


Author's solution can be found here.
Tester 1's solution can be found here.
Tester 2's solution can be found here.

This question is marked "community wiki".

asked 12 Jan '18, 19:12

wittyceaser's gravatar image

accept rate: 16%

edited 20 Feb '18, 16:57

admin's gravatar image

0★admin ♦♦

How do we prove that this gives the optimal MST?


answered 14 Jan '18, 19:56

mathecodician's gravatar image

accept rate: 7%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 12 Jan '18, 19:12

question was seen: 515 times

last updated: 20 Feb '18, 16:57