CF1681F

线段树分治做法，对于权值为 w 的边，什么情况下它会产生贡献？

假设先删除所有权值为 w 的边，此时对于权值为 w 的一条边 u, v，因为是一棵树，所以 u 的连通块和 v 的连通块此时一定不连通。

连通后会产生 siz_u * siz_v 条路径，并为每条路径贡献 1.

也就是说这条 u, v 的变会产生此时 siz_u * siz_v 的贡献。

到这里就和 P4219 BJOI4219 大融合 一样了。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
using pii = pair<int, int>;

class DSU {
  vector<int> pa, sz;
  stack<int> s;

public:
  void init(int n) {
    pa.resize(n + 1), sz.assign(n + 1, 1);
    iota(pa.begin(), pa.end(), 0);
  }
  int find(int x) { return x == pa[x] ? x : find(pa[x]); }
  void unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y)
      return;
    if (sz[x] < sz[y])
      swap(x, y);
    s.push(y);
    pa[y] = x;
    sz[x] += sz[y];
  }
  int get_time() { return s.size(); }
  int get_size(int x) { return sz[x]; }
  void undo(int time) {
    while (s.size() > time) {
      int y = s.top(), x = pa[y];
      s.pop();
      sz[x] -= sz[y];
      pa[y] = y;
    }
  }
} dsu;

vector<vector<pii>> e;
map<pii, bool> mp;
ll ans;
void dfs(int l, int r) {
  if (l == r) {
    for (auto [u, v] : e[l]) {
      u = dsu.find(u), v = dsu.find(v);
      if (u > v)
        swap(u, v);
      if (!mp[{u, v}]) {
        mp[{u, v}] = true;
        ans += 1ll * dsu.get_size(u) * dsu.get_size(v);
      }
    }
    for (auto [u, v] : e[l]) {
      u = dsu.find(u), v = dsu.find(v);
      if (u > v)
        swap(u, v);
      mp[{u, v}] = false;
    }
    return;
  }
  int tm = dsu.get_time();
  int mid = (l + r) >> 1;
  for (int i = l; i <= mid; i++) {
    for (auto [u, v] : e[i]) {
      dsu.unite(u, v);
    }
  }
  dfs(mid + 1, r);
  dsu.undo(tm);
  for (int i = mid + 1; i <= r; i++) {
    for (auto [u, v] : e[i]) {
      dsu.unite(u, v);
    }
  }
  dfs(l, mid);
  dsu.undo(tm);
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  dsu.init(n);
  e.resize(n + 1);
  for (int i = 1; i < n; i++) {
    int u, v, c;
    cin >> u >> v >> c;
    e[c].emplace_back(u, v);
  }
  dfs(1, n);
  cout << ans << endl;
  return 0;
}