题解 CF76A 【Gift】

· · 题解

思路：

提供一种题解区没有的 麻烦的要死 的 LCT 做法。

转换题意，求所有生成树 P 的

Min(Max_{i\in P}\ g_i\times G+Max_{i\in P}\ s_i\times S)

发现和 魔法森林 很像。

考虑类似的维护方式。

化边为点，先将边按 g_i 排序，然后逐条加入边，维护 s_i 的最小生成树，并在图连通后每次更新答案。

考虑如何维护 s_i 的最小生成树：

加入一条边：

于是 LCT 维护链的 Max\ s_i 即可。

考虑如何更新答案：

即要维护根节点的整棵子树的 Max\ g_i 和 Max\ s_i。

用 LCT 维护子树最值的常规手段，在每个节点开一个 multiset 维护虚子树的最值，在 access 和 link 时更新即可。

时间复杂度：O(mlog^2(n+m)) （常数极大）。

于是可以加强到 n,m\leq 10^5 。

注意最大的答案可能到 2\times 10^{18}，于是 INF 要开大。

update: 经过奆佬 @FSYolanda 的提醒，更新答案只用维护边的集合，于是用一个 set 维护可以做到 O(mlogn) (跑得挺快)。

于是可以加强到 n,m\leq 10^6 了。

code：

O(mlog^2(n+m)) 
#include <bits/stdc++.h>
using namespace std;

#define re register
#define LL long long
typedef unsigned int uint;
typedef unsigned long long ull;
#define fir first
#define sec second
#define pb push_back
#define mp make_pair

#define int long long

namespace IO {
char buf_[1 << 21], *p1_ = buf_, *p2_ = buf_;
#define ch()                                                                 \
  (p1_ == p2_ &&                                                             \
           (p2_ = (p1_ = buf_) + fread(buf_, 1, 1 << 21, stdin), p1_ == p2_) \
       ? EOF                                                                 \
       : *p1_++)
inline int in() {
  int s = 0, f = 1;
  char x = ch();
  for (; x < '0' || x > '9'; x = ch())
    if (x == '-') f = -1;
  for (; x >= '0' && x <= '9'; x = ch()) s = (s * 10) + (x & 15);
  return f == 1 ? s : -s;
}
char _buf[1 << 21];
int _pos = -1;
inline void flush() { fwrite(_buf, 1, _pos + 1, stdout), _pos = -1; }
inline void pc(char x) {
  if (_pos == (1 << 21) - 1) flush();
  _buf[++_pos] = x;
}
inline void out(int x) {
  char k[30];
  int pos = 0;
  if (!x) return pc('0');
  if (x < 0) pc('-'), x = -x;
  while (x) k[++pos] = (x % 10) | 48, x /= 10;
  for (re int i = pos; i; i--) pc(k[i]);
}
inline void out(string x) {
  int len = x.size();
  for (re int i = 0; i < len; ++i) pc(x[i]);
}
}  // namespace IO
using namespace IO;

const int A = 5e5 + 5;
const int INF = 3e18;
int n, m;
int G, S;
int ans = INF;

struct Road {
  int x, y, g, s;
  inline friend bool operator<(Road u, Road v) { return u.g < v.g; }
} p[A];

struct LCT {
  int ch[A][2], f[A], rev[A], mxg[A], mxs[A], xg[A], xs[A];
  struct MG {
    int x;
    MG(int _x = 0) { x = _x; }
    inline friend bool operator<(MG u, MG v) { return p[u.x].g > p[v.x].g; }
  };
  struct MS {
    int x;
    MS(int _x = 0) { x = _x; }
    inline friend bool operator<(MS u, MS v) { return p[u.x].s > p[v.x].s; }
  };
  multiset<MG> mg[A];
  multiset<MS> ms[A];

  inline int isroot(int x) { return ch[f[x]][0] != x && ch[f[x]][1] != x; }

  inline int Maxg(int x, int y) { return p[x].g > p[y].g ? x : y; }
  inline int Maxs(int x, int y) { return p[x].s > p[y].s ? x : y; }

  inline void pushup(int x) {
    mxg[x] =
        Maxg(Maxg(x, (*mg[x].begin()).x), Maxg(mxg[ch[x][0]], mxg[ch[x][1]]));
    mxs[x] =
        Maxs(Maxs(x, (*ms[x].begin()).x), Maxs(mxs[ch[x][0]], mxs[ch[x][1]]));
    xg[x] = Maxg(x, Maxg(xg[ch[x][0]], xg[ch[x][1]]));
    xs[x] = Maxs(x, Maxs(xs[ch[x][0]], xs[ch[x][1]]));
  }

  inline void reverse(int x) {
    if (x) swap(ch[x][0], ch[x][1]), rev[x] ^= 1;
  }

  inline void pushdown(int x) {
    if (rev[x]) reverse(ch[x][0]), reverse(ch[x][1]), rev[x] ^= 1;
  }

  inline void rotate(int x) {
    int y = f[x], z = f[y];
    int k = (ch[y][1] == x);
    if (!isroot(y)) ch[z][(ch[z][1] == y)] = x;
    f[x] = z, ch[y][k] = ch[x][k ^ 1];
    if (ch[x][k ^ 1]) f[ch[x][k ^ 1]] = y;
    ch[x][k ^ 1] = y, f[y] = x;
    pushup(y);
    return;
  }

  int st[A], top;
  inline void pushpath(int x) {
    top = 0;
    st[++top] = x;
    for (int i = x; !isroot(i); i = f[i]) st[++top] = f[i];
    for (int i = top; i; i--) pushdown(st[i]);
    return;
  }

  inline void splay(int x) {
    pushpath(x);
    while (!isroot(x)) {
      int y = f[x], z = f[y];
      if (!isroot(y)) {
        if ((ch[y][1] == x) == (ch[z][1] == y))
          rotate(y);
        else
          rotate(x);
      }
      rotate(x);
    }
    pushup(x);
    return;
  }

  inline void access(int x) {
    for (int y = 0; x; y = x, x = f[x]) {
      splay(x);
      if (y) {
        mg[x].erase(mg[x].find(MG(mxg[y])));
        ms[x].erase(ms[x].find(MS(mxs[y])));
      }
      if (ch[x][1]) {
        mg[x].insert(MG(mxg[ch[x][1]]));
        ms[x].insert(MS(mxs[ch[x][1]]));
      }
      ch[x][1] = y;
      pushup(x);
    }
  }

  inline void makeroot(int x) { access(x), splay(x), reverse(x); }

  inline int findroot(int x) {
    access(x), splay(x);
    while (ch[x][0]) pushdown(x), x = ch[x][0];
    return x;
  }

  inline void split(int x, int y) {
    makeroot(x);
    access(y);
    splay(y);
  }

  inline void link(int x, int y) {
    makeroot(x);
    if (findroot(y) != x)
      f[x] = y, mg[y].insert(MG(mxg[x])), ms[y].insert(MS(mxs[x]));
    pushup(y);
  }

  inline void cut(int x, int y) {
    makeroot(x);
    if (findroot(y) == x && f[x] == y && ch[y][0] == x) f[x] = 0, ch[y][0] = 0;
    pushup(y);
  }

  struct DSU {
    int f[A], num[A];
    inline int find(int x) { return f[x] == x ? f[x] : f[x] = find(f[x]); }
    inline void merge(int x, int y) {
      if (find(x) != find(y))
        num[find(y)] += num[find(x)], f[find(x)] = find(y);
    }
  } D;

  inline void work(int now) {
    if (D.find(p[now].x) != D.find(p[now].y)) {
      link(p[now].x + m, now);
      link(p[now].y + m, now);
      D.merge(p[now].x, p[now].y);
    } else {
      split(p[now].x + m, p[now].y + m);
      if (p[xs[p[now].y + m]].s > p[now].s) {
        int t = xs[p[now].y + m];
        cut(p[t].x + m, t), cut(p[t].y + m, t);
        link(p[now].x + m, now), link(p[now].y + m, now);
      }
    }
    if (D.num[D.find(1)] == n) {
      makeroot(m + 1);
      ans = min(ans, p[mxg[m + 1]].g * G + p[mxs[m + 1]].s * S);
    }
    return;
  }

} T;

signed main() {
  n = in(), m = in(), G = in(), S = in();
  for (int i = 1; i <= m; i++)
    p[i].x = in(), p[i].y = in(), p[i].g = in(), p[i].s = in();
  sort(p + 1, p + 1 + m);
  for (int i = 1; i <= n; i++) T.D.f[i] = i, T.D.num[i] = 1;
  for (int i = 1; i <= m; i++) T.mxg[i] = T.mxs[i] = i;
  for (int i = 1; i <= m; i++) T.work(i);
  out(ans == INF ? -1 : ans), pc('\n');
  flush();
  return 0;
}

code:

O(mlogn) 
#include <bits/stdc++.h>
using namespace std;

#define re register
#define LL long long
typedef unsigned int uint;
typedef unsigned long long ull;
#define fir first
#define sec second
#define pb push_back
#define mp make_pair

#define int long long

namespace IO {
char buf_[1 << 21], *p1_ = buf_, *p2_ = buf_;
#define ch()                                                                 \
  (p1_ == p2_ &&                                                             \
           (p2_ = (p1_ = buf_) + fread(buf_, 1, 1 << 21, stdin), p1_ == p2_) \
       ? EOF                                                                 \
       : *p1_++)
inline int in() {
  int s = 0, f = 1;
  char x = ch();
  for (; x < '0' || x > '9'; x = ch())
    if (x == '-') f = -1;
  for (; x >= '0' && x <= '9'; x = ch()) s = (s * 10) + (x & 15);
  return f == 1 ? s : -s;
}
char _buf[1 << 21];
int _pos = -1;
inline void flush() { fwrite(_buf, 1, _pos + 1, stdout), _pos = -1; }
inline void pc(char x) {
  if (_pos == (1 << 21) - 1) flush();
  _buf[++_pos] = x;
}
inline void out(int x) {
  char k[30];
  int pos = 0;
  if (!x) return pc('0');
  if (x < 0) pc('-'), x = -x;
  while (x) k[++pos] = (x % 10) | 48, x /= 10;
  for (re int i = pos; i; i--) pc(k[i]);
}
inline void out(string x) {
  int len = x.size();
  for (re int i = 0; i < len; ++i) pc(x[i]);
}
}  // namespace IO
using namespace IO;

const int A = 5e5 + 5;
const int INF = 3e18;
int n, m;
int G, S;
int ans = INF;

struct Road {
  int x, y, g, s;
  inline friend bool operator<(Road u, Road v) { return u.g < v.g; }
} p[A];

struct LCT {
  int ch[A][2], f[A], rev[A], xg[A], xs[A];
  struct MG {
    int x;
    MG(int _x = 0) { x = _x; }
    inline friend bool operator<(MG u, MG v) { return p[u.x].g > p[v.x].g; }
  };
  struct MS {
    int x;
    MS(int _x = 0) { x = _x; }
    inline friend bool operator<(MS u, MS v) { return p[u.x].s > p[v.x].s; }
  };
  multiset<MG> mg;
  multiset<MS> ms;

  inline int isroot(int x) { return ch[f[x]][0] != x && ch[f[x]][1] != x; }

  inline int Maxg(int x, int y) { return p[x].g > p[y].g ? x : y; }
  inline int Maxs(int x, int y) { return p[x].s > p[y].s ? x : y; }

  inline void pushup(int x) {
    xg[x] = Maxg(x, Maxg(xg[ch[x][0]], xg[ch[x][1]]));
    xs[x] = Maxs(x, Maxs(xs[ch[x][0]], xs[ch[x][1]]));
  }

  inline void reverse(int x) {
    if (x) swap(ch[x][0], ch[x][1]), rev[x] ^= 1;
  }

  inline void pushdown(int x) {
    if (rev[x]) reverse(ch[x][0]), reverse(ch[x][1]), rev[x] ^= 1;
  }

  inline void rotate(int x) {
    int y = f[x], z = f[y];
    int k = (ch[y][1] == x);
    if (!isroot(y)) ch[z][(ch[z][1] == y)] = x;
    f[x] = z, ch[y][k] = ch[x][k ^ 1];
    if (ch[x][k ^ 1]) f[ch[x][k ^ 1]] = y;
    ch[x][k ^ 1] = y, f[y] = x;
    pushup(y);
    return;
  }

  int st[A], top;
  inline void pushpath(int x) {
    top = 0;
    st[++top] = x;
    for (int i = x; !isroot(i); i = f[i]) st[++top] = f[i];
    for (int i = top; i; i--) pushdown(st[i]);
    return;
  }

  inline void splay(int x) {
    pushpath(x);
    while (!isroot(x)) {
      int y = f[x], z = f[y];
      if (!isroot(y)) {
        if ((ch[y][1] == x) == (ch[z][1] == y))
          rotate(y);
        else
          rotate(x);
      }
      rotate(x);
    }
    pushup(x);
    return;
  }

  inline void access(int x) {
    for (int y = 0; x; y = x, x = f[x]) splay(x), ch[x][1] = y, pushup(x);
  }

  inline void makeroot(int x) { access(x), splay(x), reverse(x); }

  inline int findroot(int x) {
    access(x), splay(x);
    while (ch[x][0]) pushdown(x), x = ch[x][0];
    return x;
  }

  inline void split(int x, int y) {
    makeroot(x);
    access(y);
    splay(y);
  }

  inline void link(int x, int y) {
    makeroot(x);
    if (findroot(y) != x) f[x] = y;
  }

  inline void cut(int x, int y) {
    makeroot(x);
    if (findroot(y) == x && f[x] == y && ch[y][0] == x) f[x] = 0, ch[y][0] = 0;
    pushup(y);
  }

  struct DSU {
    int f[A], num[A];
    inline int find(int x) { return f[x] == x ? f[x] : f[x] = find(f[x]); }
    inline void merge(int x, int y) {
      if (find(x) != find(y))
        num[find(y)] += num[find(x)], f[find(x)] = find(y);
    }
  } D;

  inline void work(int now) {
    if (D.find(p[now].x) != D.find(p[now].y)) {
      link(p[now].x + m, now);
      link(p[now].y + m, now);
      mg.insert(MG(now)), ms.insert(MS(now));
      D.merge(p[now].x, p[now].y);
    } else {
      split(p[now].x + m, p[now].y + m);
      if (p[xs[p[now].y + m]].s > p[now].s) {
        int t = xs[p[now].y + m];
        cut(p[t].x + m, t), cut(p[t].y + m, t);
        mg.erase(mg.find(t)), ms.erase(ms.find(t));
        link(p[now].x + m, now), link(p[now].y + m, now);
        mg.insert(MG(now)), ms.insert(MS(now));
      }
    }
    if (D.num[D.find(1)] == n)
      ans = min(ans, p[(*mg.begin()).x].g * G + p[(*ms.begin()).x].s * S);
    return;
  }

} T;

signed main() {
  n = in(), m = in(), G = in(), S = in();
  for (int i = 1; i <= m; i++)
    p[i].x = in(), p[i].y = in(), p[i].g = in(), p[i].s = in();
  sort(p + 1, p + 1 + m);
  for (int i = 1; i <= n; i++) T.D.f[i] = i, T.D.num[i] = 1;
  for (int i = 1; i <= m; i++) T.work(i);
  out(ans == INF ? -1 : ans), pc('\n');
  flush();
  return 0;
}