题解：P8439 Altale (Fan-made FTR 7)

· · 题解

爆标做法。我说这个题其实是 sale 有没有懂的。

我们把基环树分为两类：

注意到根在环上的三种决策中，第一种与根不在环上一致；第二种在同一个连通块中最多操作一次，因为操作了两次就不如第三种策略了。于是我们可以转化为这个问题：

给定 n 个物品，每个物品有两个价值 a_i\le b_i，花一块钱购买可以获得 a_i 的价值，花两块钱则可以获得 b_i 的价值。求获得 k 的价值至少要花多少钱。

设 d_i=b_i-a_i。我们将物品分为两类：

只要对这两种求出，花费 0\sim k 的钱最多能获得多少价值，再进行合并。

前者是好办的，直接拆成两个物品排序，贪心选一个前缀。对于后者，我们有这样一个结论：

原因很简单，因为 a_i<d_i，你选了 a_i 就没道理不把 d_i 选上，除非是被个数限制给卡了。此时按 b_i 从大到小排序，有两种情况：

前者可以枚举前缀，预处理 a_i 后缀最大值。后者同样枚举前缀，我们要干的事情是反悔掉一个 b_i-a_i 最小的位置，维护其前缀最小值即可。

至此我们解决了所有问题，排序因值域为 n 均可使用计数排序解决，总时间复杂度 \mathcal{O}(n)。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

// d0j1a_1701 fastIO 

const int MAXN = 1e6 + 10;

int head[MAXN], to[MAXN << 1], nxt[MAXN << 1], etot, d[MAXN];

inline 
void add(int u, int v) {
    ++etot, ++d[u], to[etot] = v, nxt[etot] = head[u], head[u] = etot;
    ++etot, ++d[v], to[etot] = u, nxt[etot] = head[v], head[v] = etot;
}

int s[MAXN], tp, sz[MAXN], vis[MAXN], rt[MAXN];

int n, m, cnt[MAXN], a[MAXN], b[MAXN], tot, id[MAXN];

int pos[MAXN], sum[MAXN], pre[MAXN], suf[MAXN];

int main() {
    io.read(n, m);
    for (int i = 1, u, v; i <= n; i++) io.read(u, v), add(u, v);
    for (int i = 1; i <= n; i++) sz[i] = 1;
    for (int i = 1; i <= n; i++) if (d[i] == 1) s[++tp] = i;
    for (int i = 1; i <= tp; i++) {
        int u = s[i];
        for (int _ = head[u]; _; _ = nxt[_]) {
            int v = to[_];
            if (d[v] > 1) { sz[v] += sz[u]; if (--d[v] == 1) s[++tp] = v; }
        }
    }
    for (int i = 1; i <= n; i++) --d[i];
    for (int i = 1; i <= n; i++) {
        if (vis[i]) continue; vis[i] = rt[i] = 1, s[tp = 1] = i;
        for (; tp; ) {
            int u = s[tp--];
            for (int _ = head[u]; _; _ = nxt[_]) {
                int v = to[_];
                if (!vis[v]) vis[v] = 1, s[++tp] = v;
            }
        }
    }
    for (int i = 1; i <= n; i++) vis[i] = 0;
    for (int i = 1; i <= n; i++) {
        if (rt[i] || vis[i]) continue;
        int x = 0, y = 0, c = 0; vis[i] = 1, s[tp = 1] = i;
        for (; tp; ) {
            int u = s[tp--]; ++y;
            for (int _ = head[u]; _; _ = nxt[_]) {
                int v = to[_];
                if (rt[v]) ++c;
                else if (!vis[v]) vis[v] = 1, s[++tp] = v;
                if (d[u] && !d[v] && !rt[v]) x = max(x, sz[v]);
            }
        }
        if (c == 1) ++cnt[y];
        else ++tot, a[tot] = x, b[tot] = y;
    }
    for (int i = 1; i <= tot; i++) if (a[i] * 2 >= b[i]) ++cnt[a[i]], ++cnt[b[i] - a[i]];
    tp = 0;
    for (int i = n; i; i--) for (; cnt[i]--; ++tp, s[tp] = s[tp - 1] + i);
    for (int i = 1, j = 1; i <= n; i++) {
        for (; j <= tp && s[j] < i; j++);
        if (j <= tp) pos[i] = j; else pos[i] = 1e9;
    }
    for (int i = 1; i <= n; i++) cnt[i] = 0;
    for (int i = 1; i <= tot; i++) if (a[i] * 2 < b[i]) ++cnt[b[i]];
    for (int i = n; i; i--) cnt[i] += cnt[i + 1]; tp = cnt[1];
    for (int i = tot; i; i--) if (a[i] * 2 < b[i]) id[cnt[b[i]]--] = i;
    for (int i = 1; i <= tp; i++) sum[i] = sum[i - 1] + b[id[i]];
    *pre = 1e9;
    for (int i = 1; i <= tp; i++) pre[i] = min(pre[i - 1], b[id[i]] - a[id[i]]);
    for (int i = tp; i; i--) suf[i] = max(suf[i + 1], a[id[i]]);
    auto f = [&](int x) -> int { x = m - x; return x < 0 ? 0 : pos[x]; };
    int ans = 1e9;
    for (int i = 0; i <= tp; i++) {
        ans = min(ans, i * 2 + f(sum[i]));
        if (i < tp) {
            int res = sum[i] + suf[i + 1];
            if (i) res = max(res, sum[i + 1] - pre[i]);
            ans = min(ans, i * 2 + 1 + f(res));
        }
    }
    io.write(ans);
}