生成树

· · 个人记录

等待填坑：Prim（为了卡常），boruvka，Kruskal重构树

一些题

CF1624G

分析或性质：只要一位为 1 这一位就为 1。

可以从高到低枚举位 x 贪心，将所有 x 位不为 1 的边启用（？），跑遍 dfs 判联通性，若不连通则这位必须选，否则将所有 x 位不为 1 的边删除。

CF472D

喵喵题。

对于一颗树而言，其生成树肯定唯一且就是本身，所以我们可以对给出的邻接矩阵跑生成树（最大最小皆可），然后在枚举跟算距离判断即可。

kruskal 亲测能过（毕竟我也不会 Prim/kk ）。

CF1081D

有点诈骗含量。

套路先跑最小生成树，发现至少有一条边满足删除此边后，分裂的两个联通块中各有特殊点。

则两个联通块的特殊点互相到达都要经过这条边，找到最大的满足条件的边，输出 k 次即为答案。

CF1184E3

套路题，先跑出最小生成树。

分类讨论：

考虑非树边，显然答案为非树边的端点在生成树上构成的路径的边权的最大值，这个可以直接维护 mx_{i,j} 表示点 i 向上跳 2^j 步的边权最大值，询问直接倍增。

考虑树边，对于每条树边在非树边构成的路径上的非树边，树边的权值不能大于其权值，看起来需要树剖，其实只需要将非树边按边权排序，转化为区间覆盖问题，使用并查集即可。

Code

// author : yhy
#include <bits/stdc++.h>

using namespace std;
using LL = long long;
using Pii = pair<int, int>;

const int kMaxN = 1e6 + 5, kL = 21;

int n, m, mn[kMaxN], vis[kMaxN], ans[kMaxN];
vector<Pii> e[kMaxN];

struct Node {
  int id, x, y, w;
  bool operator<(Node _) { return w < _.w; }
} v[kMaxN];
struct Dsu {
  int fa[kMaxN];
  void Init() { iota(fa + 1, fa + n + 1, 1); }
  void M(int x, int y) { fa[x] = y; }
  int GetRoot(int x) {
    return fa[x] == x ? x : fa[x] = GetRoot(fa[x]);
  }
} s1, s2;
struct LCA {
  int d[kMaxN], f[kMaxN][kL], mx[kMaxN][kL];
  void Init(int x = 1, int fa = 0) {
    f[x][0] = fa, d[x] = d[fa] + 1;
    for (int i = 1; i < kL; i++) {
      f[x][i] = f[f[x][i - 1]][i - 1];
      mx[x][i] = max(mx[x][i - 1], mx[f[x][i - 1]][i - 1]);
    }
    for (auto [nxt, w] : e[x]) {
      nxt != fa && (mx[nxt][0] = w, Init(nxt, x), 0);
    }
  }
  Pii Lca(int x, int y, int ans = 0) { // {Lca, 值}
    d[x] > d[y] && (swap(x, y), 0);
    for (int i = 0; i < kL; i++) {
      ((d[y] - d[x]) >> i & 1) && (ans = max(ans, mx[y][i]), y = f[y][i]);
    }
    if (x == y) return {x, ans};
    for (int i = kL - 1; i >= 0; i--) {
      f[y][i] != f[x][i] && (ans = max(ans, max(mx[x][i], mx[y][i])), x = f[x][i], y = f[y][i]);
    }
    return {f[x][0], max(ans, max(mx[x][0], mx[y][0]))};
  }
} l;

signed main() {
  cin.tie(0)->ios::sync_with_stdio(0);
  cin >> n >> m, s1.Init();
  for (int i = 1; i <= m; i++) {
    cin >> v[i].x >> v[i].y >> v[i].w, v[i].id = i;
  }
  sort(v + 1, v + m + 1);
  for (int i = 1; i <= m; i++) {
    int fx = s1.GetRoot(v[i].x), fy = s1.GetRoot(v[i].y);
    if (fx != fy) {
      s1.M(fx, fy), vis[i] = 1;
      e[v[i].x].push_back({v[i].y, v[i].w});
      e[v[i].y].push_back({v[i].x, v[i].w});
    }
  }
  l.Init(1, 0), s2.Init();
  fill(mn + 1, mn + n + 1, 1e9);
  for (int i = 1; i <= m; i++) {
    if (!vis[i]) {
      int x = s2.GetRoot(v[i].x), y = s2.GetRoot(v[i].y);
      auto [lca, mx] = l.Lca(v[i].x, v[i].y); ans[v[i].id] = mx;
      for (; l.d[x] > l.d[lca]; x = s2.GetRoot(x)) {
        mn[x] = v[i].w, s2.M(x, s2.GetRoot(l.f[x][0]));
      }
      for (; l.d[y] > l.d[lca]; y = s2.GetRoot(y)) {
        mn[y] = v[i].w, s2.M(y, s2.GetRoot(l.f[y][0]));
      }
    }
  }
  for (int i = 1; i <= m; i++) {
    if (vis[i]) {
      ans[v[i].id] = mn[l.d[v[i].x] < l.d[v[i].y] ? v[i].y : v[i].x];
    }
  }
  for (int i = 1; i <= m; i++) {
    cout << ans[i] << '\n';
  }
}