PROBLEM LINK:
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:
 Provide 2 nonempty, nonintersectin 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.
 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

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.

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.