求助为什么报错
  • 板块灌水区
  • 楼主yhylivedream
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/7/1 21:14
  • 上次更新2024/7/1 21:17:15
查看原帖
求助为什么报错
778022
yhylivedream楼主2024/7/1 21:14
// author : yhy
#include <bits/stdc++.h>

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

const int kMaxN = 3e5 + 5;

int n, m, q, l[kMaxN];

template <typename T, const int N>
class Dsu {
 public:
  int F(int x) {
    !fa[x] && (fa[x] = x);
    return fa[x] == x ? x : fa[x] = F(fa[x]);
  }
  void M(int x, int y) {
    F(x) != F(y) && (fa[F(x)] = F(y));
  }
 private:
  T fa[N + 5] = {0};
};

template <typename T, const int N>
class TrList {
#define Pit pair<int, T>
 public:
  void Ad(int x, int y, T w = 1) {
    e[x].emplace_back(y, w);
  }
  void As(int x, int y, T w = 1) {
    e[x].emplace_back(y, w), e[y].emplace_back(x, w);
  }
  T Calc(int rt, T kInf) {
    fill(f + 1, f + N + 1, 0);
    T mx = -kInf; S(rt, 0, mx);
    return mx;
  }
  void S(int x, int fa, T &mx) {
    for (Pit e : e[x]) {
      if (e.first != fa) {
        S(e.first, x), mx = max(mx, f[x] + f[e.first] + e.second);
        f[x] = max(f[x], f[e.first] + e.second, mx);
      }
    }
  }

 private:
  T f[N + 5];
  vector<Pit> e[N + 5];
};

Dsu<int, 300000> d;
TrList<int, 300000> tr;

signed main() {
  cin.tie(0)->ios::sync_with_stdio(0), cin >> n >> m >> q;
  for (int i = 1, x, y; i <= m; i++) {
    cin >> x >> y, tr.As(x, y), d.M(x, y);
  }
  for (int i = 1; i <= n; i++) {
    if (d.F(i) == i) {
      l[i] = tr.Calc(i, 1e9);
    }
  }
  for (int ty, x, y; q--;) {
    cin >> ty >> x;
    if (ty == 1) {
      cout << l[d.F(x)] << '\n';
    } else {
      cin >> y, d.M(x, y);
      int v = max(l[d.F(x)], l[d.F(y)]);
      l[d.F(y)] = max(v, (l[d.F(x)] + 1) / 2 + (l[d.F(y)] + 1) / 2 + 1);
    }
  }
  return 0;
}
2024/7/1 21:14
加载中...