CF1824E LuoTianyi and Cartridge
Alex_Wei
·
·
题解
CF1824E LuoTianyi and Cartridge
先考虑对某个 $v$ 求答案。显然，若一条边一侧没有被选中的点，则该边一定不会被选中。反之，若每条被选中的边两侧均有被选中的点，则一定合法：按任意顺序加入选中的边，其两侧必然存在被选择的 $u, v$ 不连通，否则 $T'$ 已经形成一个连通块，矛盾。
将不合法的边两端合并起来，得到一棵树 $G$，树上每条边代表一条合法边，每个点代表若干个点（可以全都是非法点），且叶子对应至少一个合法点：若叶子不对应任何合法点，则将其和与其相连的唯一的边删去不影响答案，因为该边不可能被选中。
此外，一个叶子至少有一个点被选中，否则与其相连的唯一的边无法被选中，往 $T'$ 加入该边和叶子内任意合法点，方案仍合法且权值增大。
因此，对于固定的 $x = \min(A, C)$，可以算出 $T'$ 的边数 $e = \min(|V| - 1, |E|)$，其中 $V, E$ 是删去了不合法的元素的点集和边集。
- 选点：选择所有叶子的权值最大的合法点，以及其它所有合法点的权值前 “$e + 1$ 减去叶子数量” 大的点。
- 选边：选择权值前 $e$ 大的合法边。
考虑实时维护 $G$：
- 对每个点 $u\in V_G$，记录 $S_u$ 表示对应所有合法点的权值。
- 对每个点 $u\in V_G$，记录 $X_u$ 表示它在树上的所有邻边。
- 维护所有叶子权值最大的合法点的点权之和 $L$。
- 维护所有合法边权值构成的权值线段树 $T_D$。
- 维护所有合法点去掉每个叶子权值最大的合法点的点权构成权值线段树 $T_B$。
- 一个点是叶子当且仅当 $|X_u| = 1$。
考虑 $x$ 在增大的过程中，会删去一些边或一些点。
对于删边，直接合并两侧的点，注意 $S$ 和 $X$ 需要启发式合并。
对于删点，若删去后得到了空叶子，则删除该叶子和与其相连的唯一的边。注意这个过程可能引发连锁反应（一个空心非叶子是合法的，所以删边可能导致某个空心非叶子变成空心叶子），用队列维护。
时间复杂度 $\mathcal{O}(n\log ^ 2 n)$ 或 $\mathcal{O}(n\log n)$（线段树合并维护 $S$，$X$ 可以额外维护度数并懒惰删除将 `set` 换成 `vector`）。
```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ull = unsigned long long;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
constexpr int mod = 1e9 + 7;
void addt(int &x, int y) {x += y, x >= mod && (x -= mod);}
int add(int x, int y) {return x += y, x >= mod && (x -= mod), x;}
int ksm(int a, int b) {
int s = 1;
while(b) {
if(b & 1) s = 1ll * s * a % mod;
a = 1ll * a * a % mod, b >>= 1;
}
return s;
}
bool Mbe;
constexpr int N = 2e5 + 5;
struct SegTree {
int cnt[N << 2];
ll val[N << 2];
void modify(int l, int r, int p, int x, int v) {
cnt[x] += v, val[x] += v * p;
if(l == r) return;
int m = l + r >> 1;
if(p <= m) modify(l, m, p, x << 1, v);
else modify(m + 1, r, p, x << 1 | 1, v);
}
ll binary(int l, int r, int x, int c) {
if(l == r) return 1ll * c * l;
int m = l + r >> 1;
if(cnt[x << 1 | 1] >= c) return binary(m + 1, r, x << 1 | 1, c);
return val[x << 1 | 1] + binary(l, m, x << 1, c - cnt[x << 1 | 1]);
}
} B, D;
ll ans, val, L;
bool ban[N];
int a[N], b[N], c[N], d[N];
int n, p[N];
int fa[N];
set<pii> g[N];
multiset<int> S[N];
int find(int x) {return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);}
void dele(int id, int u, int v) {
g[u].erase(g[u].lower_bound({id, 0}));
g[v].erase(g[v].lower_bound({id, 0}));
ban[id] = 1;
D.modify(1, N, d[id], 1, -1);
}
struct edge {
int u, v, id;
bool operator < (const edge &x) const {
return c[id] < c[x.id];
}
} e[N];
void solve() {
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) {
cin >> b[i], S[i].insert(b[i]);
val += b[i], B.modify(1, N, b[i], 1, 1);
ans = max(ans, 1ll * a[i] * b[i]);
}
for(int i = 1; i <= n; i++) fa[i] = p[i] = i;
for(int i = 1; i < n; i++) {
int x, y;
cin >> x >> y >> c[i] >> d[i];
g[x].insert({i, y});
g[y].insert({i, x});
e[i] = {x, y, i};
val += d[i], D.modify(1, N, d[i], 1, 1);
}
for(int i = 1; i <= n; i++) {
if(g[i].size() > 1) continue;
B.modify(1, N, b[i], 1, -1), L += b[i];
}
sort(e + 1, e + n);
sort(p + 1, p + n + 1, [&](int x, int y) {return a[x] < a[y];});
for(int i = 1, pe = 1, pid = 1; i < N; i++) {
int upd = 0;
auto pro = [&](int id, int coe) {
if(g[id].size() != 1) return;
L += coe * *--S[id].end();
B.modify(1, N, *--S[id].end(), 1, -coe);
};
while(pe < n && c[e[pe].id] < i) {
int id = e[pe].id, x = find(e[pe].u), y = find(e[pe].v); pe++;
if(ban[id]) continue;
upd = 1, pro(x, -1), pro(y, -1), dele(id, x, y);
if(S[x].size() < S[y].size()) swap(S[x], S[y]);
if(g[x].size() < g[y].size()) swap(g[x], g[y]);
for(int it : S[y]) S[x].insert(it);
for(auto it : g[y]) g[x].insert(it);
fa[y] = x, pro(x, 1);
}
while(pid <= n && a[p[pid]] < i) {
int id = p[pid], ff = find(id); pid++;
upd = 1, pro(ff, -1);
S[ff].erase(S[ff].find(b[id]));
B.modify(1, N, b[id], 1, -1);
if(S[ff].empty() && g[ff].size() == 1) {
queue<int> q;
q.push(ff);
while(!q.empty()) {
int t = q.front();
q.pop();
for(auto it = g[t].begin(); it != g[t].end(); ) {
auto nxt = it; nxt++;
int id = it->first, to = find(it->second);
dele(id, t, to);
if(g[to].size() == 1) {
if(S[to].empty()) q.push(to); // id -> to
else pro(to, 1); // id -> to
}
it = nxt;
}
}
}
else pro(ff, 1);
}
if(!D.cnt[1]) break;
if(upd) {
int E = D.cnt[1], V = n - pid + 1;
int m = min(E, V - 1), mm = V - B.cnt[1];
val = L;
val += D.binary(1, N, 1, m);
val += B.binary(1, N, 1, m + 1 - mm);
}
ans = max(ans, i * val);
}
cout << ans << "\n";
}
bool Med;
int main() {
fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T = 1;
// cin >> T;
while(T--) solve();
cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
return 0;
}
```