题解 CF566E 【Restoring Map】

> [CF566E Restoring Map](https://codeforces.com/contest/566/problem/E) ## 题意 - 有一棵 $n$ 个点的树，你不知道这棵树的边是怎么连的。 - 你得到了 $n$ 条关于每个点信息，每条信息记录了距离某一个点 $\le 2$ 的所有点。 - 但你不知道每条信息具体是哪个点的。 - 你需要构造一棵满足这些信息的树。 - $n \le 10^3$。 ## 题解 我们将**叶子节点**定义为**度数为 $1$** 的节点，**非叶节点**定义为**度数 $>1$** 的节点。 首先我们来考虑大部分情况，即**至少有三个非叶节点**的情况。 在这种情况下，**两个非叶节点 $(x,y)$ 之间存在边，当且仅当存在两个集合的交为 $\{x,y\}$**。 于是可以得到所有非叶节点之间的连边，bitset 优化即可做到 $\mathcal O(\frac{n^3}w)$。 **值得一提的是，如果当存在两个集合的交集大小为 $2$ 时，对 bitset 暴力 `for` 循环找值为 $1$ 的位置，复杂度并不会除以那个 $w$，是错的，可以被卡掉，但不知道为什么 CF 没有卡，也许是因为 CF 评测机太快了。正确的写法是借用 `_Find_first()` 和 `_Find_next()` 函数，前者是找到 bitset 中从低位到高位第一个 $1$ 的位置，后者是找到当前位置的下一个为 $1$ 的位置，这样复杂度才会除以那个 $w$。** 现在，我们知道每个点是否是叶子节点，接下来考虑如何找到叶子节点在树中的父亲。 显然，**对于每个叶子节点，在所有包含它的集合中，节点数最少的集合一定就是此叶子节点的集合**。因此我们可以确定每个叶子节点对应的集合是哪个。 如果我们把**连边集合**定义为**一个非叶节点与和它相连的非叶节点**构成的集合，可以发现，**一个叶子节点的集合中去掉所有叶子节点**等于**其父亲的连边集合**，而所有非叶节点的连边集合一定互不相同，那么我们就可以确定所有叶子节点的父亲了，这里同样可以 bitset 优化。 最后来考虑非叶节点数量少于三个的情况。 如果不存在非叶节点，则 $n=2$，可以直接判掉。 如果只有一个非叶节点，那就意味着所有集合都是 $\{1,2,\cdots n\}$，也可以直接判掉。 如果有两个非叶节点，我们先采用至少三个非叶节点的方法找到这两个非叶节点，然后会发现这两个非叶节点的连边集合是一样的。但是，这个时候叶子的集合就只有两种，选其中一种里的叶子挂在一个非叶节点下，另一种里的叶子挂在另外一个非叶节点下就好了。 总时间复杂度 $\mathcal O(\frac{n^3}w)$。 ## 代码 ```cpp const int N = 1e3 + 7; int n, v[N], w[N], cnt; bitset<N> a[N], b[N], e[N]; int main() { rd(n); if (n == 2) return prints("1 2"), 0; bool ok = 1; for (int i = 1, j, k; i <= n; i++) { rd(k); if (k != n) ok = 0; while (k--) rd(j), a[i][j] = 1; } if (ok) { for (int i = 1; i < n; i++) print(n, ' '), print(i); return 0; } for (int i = 1; i <= n; i++) for (int j = i + 1; j <= n; j++) { bitset<N> o = a[i] & a[j]; if (o.count() != 2) continue; int x = o._Find_first(), y = o._Find_next(x); if (e[x][y]) continue; print(x, ' '), print(y); e[x][y] = e[y][x] = 1, v[x] = v[y] = 1; } for (int i = 1; i <= n; i++) if (!v[i]) { int s = n + 1, o = 0; for (int j = 1; j <= n; j++) if (!w[j] && a[j][i]) { int c = a[j].count(); if (c < s) s = c, o = j; } b[i] = a[o], w[o] = 1; } else e[i][i] = 1, ++cnt; if (cnt == 2) { int x, y; for (int i = 1; i <= n; i++) if (v[i]) x = i; for (int i = n; i; i--) if (v[i]) y = i; for (int i = 1; i <= n; i++) if ((int)a[i].count() != n) { for (int j = 1; j <= n; j++) { if (v[j]) continue; if (a[i][j]) print(x, ' '); else print(y, ' '); print(j); } break; } return 0; } for (int i = 1; i <= n; i++) if (!v[i]) { for (int j = 1; j <= n; j++) if (!v[j]) b[i][j] = 0; for (int j = 1; j <= n; j++) if (v[j] && b[i] == e[j]) { print(i, ' '), print(j); break; } } return 0; } ```