# SPANTREE - Editorial

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

### PROBLEM

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.

#### Constraints:

2 \le N \le 1000

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

### EXPLANATION

#### 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).

#### Approach

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 AND TESTERâ€™S SOLUTIONS:

Authorâ€™s solution can be found here.
Tester 1â€™s solution can be found here.
Tester 2â€™s solution can be found here.

1 Like

How do we prove that this gives the optimal MST?

1 Like