CF2222F

题意：给定一张图，现在要选一些点，问让这些点连通的代价最小是多少。

$dis(u, v)=MEX(road(u, v))$

在新图上，两个点之间有权值为 $w$ 的连边，当且仅当在旧图上存在一条路径 $u, v$，使得路径的 MEX 值为 $w$。

如果我们知道所有的 $dis$，那么这就是一个最小生成树问题。

最小生成树的逻辑是从小到大枚举可能的边，如果两个点不连通，那么就加入这条边让两个点连通。

MEX 的范围是 $[0, m]$，因为最多只有 $m$ 条边，如果要产生 $m + 1$ 的 MEX，就需要至少 $m + 1$ 条边。

枚举 $w:0\to m$，找是否存在一条权值为 $w$ 的路径。

如果存在这样一条边，说明连接 $u, v$ 的所有的边的值都不等于 $w$，此时路径的权值一定小于等于 $w$，而因为我们是从小到大枚举的，如果 MEX 比 $w$ 更小的话，那么在之前这条边就已经加过，$u, v$ 已经连通，所以一定等于 $w$。

我们每次优先向左递归，这样就保证了最小生成树的贪心。

本质上： 线段树分治的前序遍历（先左后右），天然保证了我们传给并查集的 MEX 权值是严格单调递增的。这完美替代了常规 Kruskal 算法中对边权排序的步骤。

也就是说，我们从小到大枚举 $w$，对于每个 $w$，把权值等于 $w$ 边删掉，剩下的边加入到并查集中，此时可以连通的两个点的权值就一定是 $w$。

暴力的做法就是枚举 $w$，每次暴力新建一个并查集。

考虑线段树二分+可撤销并查集。

从 $[0, m]$ 区间开始递归，每次优先递归左边，然后将值在右半部分的边加入到并查集。

缺少左半部分，此时的 MEX 为 l，在合并的过程中，我们需要知道两个连通块中是否各自包含一个新图上的点，如果是，那么就将其添加到最小生成树中，合并两个集合。

所以需要为并查集维护一个代表元，初始时，只有新图中的点代表元是它本身，其它点的代表元是 0.

合并时，更新父节点的代表元（如果没有）。如果合并前两个连通块都有各自的代表元，说明这两个代表元之间可以连一条权值为 l 的边，但假如在最小生成树上这两个点已经连通了，这说明这两个代表元之间可能在之前通过更小的 MEX 连通了，所以就无需添加到最小生成树当中。

问题来了，所有合并都已完成时，并查集内的点两两都是可以连一条长度为 l 的边的。合并的过程中，一个连通块内部可能不止一个在新图中的点，这样做对吗？

想象这样一种情况，对于每条边都相同的图，建一颗最小生成树，那肯定是怎么建都可以，有很多种情况，连哪条边都一样。

所以各只选一个点当代表元没问题，两个连通块想要变得连通，选任意一条边即可。

我们实际上维护了一个动态的边集，递归到 $[l, r]$ 时，图是由 $[0, l]$ 和 $[r + 1, m]$ 的边组成的，递归到底时，所有的答案都已经处理完成。

我们利用回滚操作，利用了所有的中间状态，从而优化了时间复杂度。

对于这样一个线段树形状的结构，按照原来暴力的思路，除了值为 0 以外所有的边的集合，实际上就在所有左端点为 0 的 Node 上被动态处理了，从顶层开始，每次往并查集中添加 n / 2, n / 4, … 范围的边，最终边集变成了和暴力一样的值域大小为 $[1, 2^n]$ 的所有边。

时间复杂度：

只有启发式合并的并查集，深度在 $\log n$ 级别，单次操作的复杂度是 $\log n$。

分治树的深度是 $\log m$，每一层中每条边都要添加/删除一次，于是总复杂度为 $m\log m logn$。

Tricks：

• 因为要让并查集支持撤销操作，路径压缩会复杂度爆表。
  • 为什么？路径压缩的本质是在查询时将长长的树链变成一个点，用一次高昂的代价换取后续的 $O(1)$ 查询，因为并查集的结构是固定的，根节点不会变。但是对于随时撤销的并查集来说，也许刚进行完一次路径压缩，就撤销了。频繁的路径压缩代价很大，撤销也需要很大的代价，比如将 $x, y$ 合并，$y$ 的所有子节点都要挂到 $x$ 上，撤销的时候又要重新连接到 $y$ 上，所以不能使用路径压缩。
• 利用函数重载可以定义不同参数的函数。
• 可撤销并查集实现可以用栈来记录撤销需要用到的信息，然后利用撤销前的栈大小作为时间戳，优雅撤销。
• 新图可能存在自环，而自环的 MEX 是 0，所以去一下重就可以了。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9 + 7;
#define fi first
#define se second
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pil = pair<int, ll>;
using pll = pair<ll, ll>;

class DSU {
  vector<int> fa, sz, repr;

public:
  void init(int n) {
    fa.resize(n + 1);
    sz.assign(n + 1, 1);
    iota(fa.begin(), fa.end(), 0);
  }
  void init(int n, vector<bool> &inC) {
    fa.resize(n + 1);
    sz.assign(n + 1, 1);
    repr.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) {
      if (inC[i])
        repr[i] = i;
    }
    iota(fa.begin(), fa.end(), 0);
  }
  int get(int x) { return sz[find(x)]; }
  int find(int u) { return fa[u] == u ? u : find(fa[u]); }
  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y)
      return false;
    if (sz[y] > sz[x])
      swap(x, y);
    fa[y] = x;
    sz[x] += sz[y];
    return true;
  }
  pair<int, int> unite(int x, int y, stack<array<int, 2>> &s) {
    x = find(x), y = find(y);
    if (x == y)
      return {-1, -1};
    if (sz[y] > sz[x])
      swap(x, y);
    int &u = repr[x], &v = repr[y];
    s.push({y, u});
    fa[y] = x;
    sz[x] += sz[y];
    if (u && v)
      return {u, v};
    if (!u)
      u = v;
    return {-1, -1};
  }
  void roll_back(int time, stack<array<int, 2>> &s) {
    while (s.size() > time) {
      auto [y, pr] = s.top();
      s.pop();
      int x = fa[y];
      repr[x] = pr;
      sz[x] -= sz[y];
      fa[y] = y;
    }
  }
} dsu, mst;

void solve() {
  int n, m, q, color = 0, c = -1;
  cin >> n >> m >> q;
  vector<vector<pii>> e(m + 1, vector<pii>());
  vector<bool> inC(n + 1);
  for (int i = 0, u, v, w; i < m; i++) {
    cin >> u >> v >> w;
    e[w].emplace_back(u, v);
  }
  for (int i = 0, x; i < q; i++) {
    cin >> x;
    if (c == -1)
      c = x;
    if (!inC[x]) {
      inC[x] = true;
      color++;
    }
  }
  dsu.init(n, inC), mst.init(n);
  ll ans = 0;
  stack<array<int, 2>> s;
  auto add = [&](int u, int v, int mex) {
    auto [up, vp] = dsu.unite(u, v, s);
    if (up != -1 && vp != -1) {
      if (mst.unite(up, vp))
        ans += mex;
    }
  };
  function<void(int, int)> dfs = [&](int l, int r) {
    if (l == r) {
      return;
    }
    int mid = (l + r) >> 1;
    auto cnt = s.size();
    for (int i = mid + 1; i <= r; i++) {
      for (auto [u, v] : e[i]) {
        add(u, v, l);
      }
    }
    dfs(l, mid);
    dsu.roll_back(cnt, s);
    for (int i = l; i <= mid; i++) {
      for (auto [u, v] : e[i]) {
        add(u, v, mid + 1);
      }
    }
    dfs(mid + 1, r);
    dsu.roll_back(cnt, s);
  };
  dfs(0, m);
  if (mst.get(c) != color)
    cout << -1 << endl;
  else
    cout << ans << endl;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int T;
  cin >> T;
  while (T--)
    solve();
  return 0;
}

dsu 负责维护局部连通性，在分治中不断更新和回滚。mst 负责维护最小生成树并累加答案。