Sometimes Naive

4594C Sometimes Naive

Summarize

一棵$n$个节点的有根树，除根外所有节点的出边都指向其父亲，求一个节点，使得所有选中的点到其路径长度和最小，求此时所有路径经过的点的颜色数。

$1 \le n \le 3000$

感谢@oy 的贡献

Solution

神仙题

虽然做完后想想不是很难……但哪道题不是如此呢TAT

易得每次询问中 $c$ 个人的集合点为 $\text{lca}(v_1,v_2,..,v_c)$ 。每个人到集合点的路径上所经过的特产看作一个集合。可以采用倍增和 bitset 优化求出所有的集合，由于本题卡空间，倍增需要使用滚动数组。代码实现非常致郁。

在预处理出集合信息后，考虑如何回答询问。不妨二分答案 $ans$，构造二分图 $G$：二分图左侧有 $c\times ans$ 个节点，表示共 $c$ 个人，每人购买 $ans$ 个物品；右侧有 $m$ 个节点，表示所有特产。如果某个人可以购买特产 $k$ （即 $k$ 在此人到集合点的路径上），则在对应节点间连边。不难发现，如果存在使左侧节点全部匹配的完备匹配，则 $ans$ 合法。

考虑优化。

Hall 定理：

记 $M(X)$ 表示与点集 $X$ 直接相连的点集。

如果二分图 $G$ 中，$\forall X\in U,|X|\le |M(X)|$ 则二分图 $G$ 存在完备匹配。

因此我们只需枚举二分图点集中的所有子集，即可判断 $ans$ 是否合法。

进一步观察可以发现，$M(U)$ 与二分出的 $ans$ 无关，而 $|X|=|U|\times ans$。也就是说，我们需要找到一个最大的 $ans$，使得 $|U|\times ans\le |M(U)|$ 恒成立。因此不必二分答案，直接求解 $ans=\min\lbrace|M(U)|/|U|\rbrace$ 即可。

代码虽不长却极端致郁。

Code

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 300005;
const int MAXQ = 50005;
const int INF = 0x3f3f3f3f;

int n, m, q;
int f[MAXN][21], dep[MAXN];
int h[MAXQ][6], c[MAXN], a[MAXQ][6], t[MAXN][21];
bitset<1005> g[MAXN]; 
bitset<1005> s[MAXQ][6]; 
bitset<1005> x[35]; 

inline int Lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int i = 19; i >= 0; --i)
        if (dep[f[u][i]] >= dep[v]) u = f[u][i];
    if (u == v) return u;
    for (int i = 19; i >= 0; --i)
        if (f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
    return f[u][0];
}

int main() {
    scanf("%d%d%d", &n, &m, &q);
    dep[1] = 1;
    for (int i = 2; i <= n; ++i)
        scanf("%d", &f[i][0]), dep[i] = dep[f[i][0]] + 1;
    for (int j = 1; j <= 19; ++j)
        for (int i = 1; i <= n; ++i)
            f[i][j] = f[f[i][j - 1]][j - 1];
    for (int i = 1; i <= n; ++i) {
        int tmp;
        scanf("%d", &tmp);
        g[i][tmp] = 1;
    }
    for (int i = 1; i <= q; ++i) {
        scanf("%d", &c[i]);
        for (int j = 1; j <= c[i]; ++j) scanf("%d", &a[i][j]), s[i][j] = g[a[i][j]];
        int lca = a[i][1];
        for (int j = 2; j <= c[i]; ++j) lca = Lca(lca, a[i][j]);
    	for (int j = 1; j <= c[i]; ++j) h[i][j] = dep[a[i][j]] - dep[lca];
    }
    for (int i = n; i >= 1; --i) g[i] |= g[f[i][0]];
    for (int j = 0; j <= 19; ++j) {
        for (int i = 1; i <= q; ++i) 
            for (int k = 1; k <= c[i]; ++k)
                if (h[i][k] & (1 << j)) s[i][k] |= g[a[i][k]], a[i][k] = f[a[i][k]][j];
        for (int i = n; i >= 1; --i) g[i] = (g[i] | g[f[i][j]]);
    }
    for (int i = 1; i <= q; ++i) {
        int ans = INF;
        for (int k = 1; k < (1 << c[i]); ++k) {
            x[k].reset();
            int tmp = 0;
            for (int j = 1; j <= c[i]; ++j) 
                if (k & (1 << (j - 1))) 
                    tmp++, x[k] |= s[i][j];
            ans = min(ans, (int)x[k].count() / tmp);
        }
        printf("%d\n", ans * c[i]);
    }
    return 0;
}

# 二分图匹配, 最近公共祖先

Sometimes Naive

Summarize

Solution

Code

Comments

一言（ヒトコト）

Recent

Categories

Tag Cloud

Your browser is out-of-date!