#分治

2024牛客多校2B MST

ProblemSajin最近深入研究了最小生成树，现在他已经掌握了MST的算法。他渴望通过一系列查询来评估您对最小生成树概念的掌握程度。 您将面临一个加权无向图，该图包含没有任何自环的 个顶点和 条边。 Sajin提出 询问。对于每个顶点集，都给出了一个顶点集 。您的目标是确定 的诱导子图（induced subgraph）并找到其最小生成树的权重。如果 的诱导子图断开，则输出-1。 图的诱导子图是另一个图，由图的顶点子集和原始图中的所有边组成，连接该子集中的顶点对。即，对于图 ，给定 ，则有 ，诱导子图为 。