恒生电子笔试t3题解

#恒生电子笔试#

题目：无环树求所有路径最大值的和

笔试的时候没写出来，想到了边权按贡献算，但只写了个暴力20%。

正解：并查集
每个点视为一个联通块，先按边权从小到大排序，逐个加入边。联通块里的值肯定都小于当前边权，那么左右联通块大小就分别代表边左右两侧的节点数，相乘就是路径数。所以贡献 = 左边连通块大小 × 右边连通块大小 × 边权。

代码如下
struct edge {
  int u, v, w;
  edge(int u = 0, int v = 0, int w = 0) : u(u), v(v), w(w) {}
  bool operator<(const edge &other) const { return w < other.w; }
};
ll res = 0, n;
vector<edge> e;
int fa[N], sz[N];
int find(int x) { return fa[x] = ((fa[x] == x) ? x : find(fa[x])); }
void unite(int x, int y) {
  int rx = find(x), ry = find(y);
  if (rx == ry)
    return;
  if (sz[rx] < sz[ry])
    swap(rx, ry);
  fa[ry] = rx, sz[rx] += sz[ry];
}
void solve() {
  cin >> n;
  for (int i = 1; i < n; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    e.emplace_back(u, v, w);
  }
  for (int i = 1; i <= n; i++) {
    fa[i] = i, sz[i] = 1;
  }
  sort(e.begin(), e.end());
  for (const auto &e : e) {
    int ru = find(e.u);
    int rv = find(e.v);
    if (ru != rv) {
      // 贡献 = 左边连通块大小 × 右边连通块大小 × 边权
      res = (res + (ll)sz[ru] * sz[rv] % mod * e.w % mod) % mod;
      unite(e.u, e.v);
    }
  }
  cout << res << endl;
}