q

lihefan · 2023-06-18 16:41:52 · 题解

这道题是一道比较经典的分治题目，需要我们用到分治思想解题。我们把图进行递归地二分，在每个子图中进行划分找到 k_i 以及对应的划分方案 S_i ，然后进行合并即可。

考虑如何递归二分图。首先二分 V，森林就变成了若干个树。此时，每个点所属的集合只有两种情况，要么在左半部分，要么在右半部分，于是考虑显式地描述状态：f(i,S_1,S_2,X,Y)，其中 i 表示当前处理到的点的下标，S_1 和 S_2 分别表示与当前结点在一棵树中的前者/后者所有点的集合（与当前点不连通的点），X 表示已经划分出来的子集的数目，Y 表示在 [X+1,t] 中的第一个还没有被计算的子集的下标。我们可以将点按照 DFS 序排列，这样对于每个点 i，我们可以通过 i 的 DFS 子树所有节点的位置区间来确定他所属的集合（左半部分和右半部分之一）。因此，严格来讲，我们的状态中还可以增加一个参数，表示当前处理的状态对应的结点集合大小之和，以保证每个集合都不超过 k。

考虑如何计算 f。我们显然需要递归地计算出 f(i-1,S_1',S_2',X',Y')。于是枚举与 i 相邻的点 j，此时有两种情况：

这个操作描述地比较麻烦，实际上可以看做是从 V_X 中新增了一个点，其它点继续沿用之前的划分方案即可。因此，我们对答案贡献的统计就没有必要按照式子计算了，只需要记录下最小值即可，在递归返回时进行合并。最后将整张图二分即可。

代码如下：这道题是一道比较经典的分治题目，需要我们用到分治思想解题。我们把图进行递归地二分，在每个子图中进行划分找到 k_i 以及对应的划分方案 S_i ，然后进行合并即可。

考虑如何递归二分图。首先二分 V，森林就变成了若干个树。此时，每个点所属的集合只有两种情况，要么在左半部分，要么在右半部分，于是考虑显式地描述状态：f(i,S_1,S_2,X,Y)，其中 i 表示当前处理到的点的下标，S_1 和 S_2 分别表示与当前结点在一棵树中的前者/后者所有点的集合（与当前点不连通的点），X 表示已经划分出来的子集的数目，Y 表示在 [X+1,t] 中的第一个还没有被计算的子集的下标。我们可以将点按照 DFS 序排列，这样对于每个点 i，我们可以通过 i 的 DFS 子树所有节点的位置区间来确定他所属的集合（左半部分和右半部分之一）。因此，严格来讲，我们的状态中还可以增加一个参数，表示当前处理的状态对应的结点集合大小之和，以保证每个集合都不超过 k。

考虑如何计算 f。我们显然需要递归地计算出 f(i-1,S_1',S_2',X',Y')。于是枚举与 i 相邻的点 j，此时有两种情况：

这个操作描述地比较麻烦，实际上可以看做是从 V_X 中新增了一个点，其它点继续沿用之前的划分方案即可。因此，我们对答案贡献的统计就没有必要按照式子计算了，只需要记录下最小值即可，在递归返回时进行合并。最后将整张图二分即可。

代码如下：这道题是一道比较经典的分治题目，需要我们用到分治思想解题。我们把图进行递归地二分，在每个子图中进行划分找到 k_i 以及对应的划分方案 S_i ，然后进行合并即可。

考虑如何递归二分图。首先二分 V，森林就变成了若干个树。此时，每个点所属的集合只有两种情况，要么在左半部分，要么在右半部分，于是考虑显式地描述状态：f(i,S_1,S_2,X,Y)，其中 i 表示当前处理到的点的下标，S_1 和 S_2 分别表示与当前结点在一棵树中的前者/后者所有点的集合（与当前点不连通的点），X 表示已经划分出来的子集的数目，Y 表示在 [X+1,t] 中的第一个还没有被计算的子集的下标。我们可以将点按照 DFS 序排列，这样对于每个点 i，我们可以通过 i 的 DFS 子树所有节点的位置区间来确定他所属的集合（左半部分和右半部分之一）。因此，严格来讲，我们的状态中还可以增加一个参数，表示当前处理的状态对应的结点集合大小之和，以保证每个集合都不超过 k。

考虑如何计算 f。我们显然需要递归地计算出 f(i-1,S_1',S_2',X',Y')。于是枚举与 i 相邻的点 j，此时有两种情况：

这个操作描述地比较麻烦，实际上可以看做是从 V_X 中新增了一个点，其它点继续沿用之前的划分方案即可。因此，我们对答案贡献的统计就没有必要按照式子计算了，只需要记录下最小值即可，在递归返回时进行合并。最后将整张图二分即可。

代码如下：这道题是一道比较经典的分治题目，需要我们用到分治思想解题。我们把图进行递归地二分，在每个子图中进行划分找到 k_i 以及对应的划分方案 S_i ，然后进行合并即可。

考虑如何递归二分图。首先二分 V，森林就变成了若干个树。此时，每个点所属的集合只有两种情况，要么在左半部分，要么在右半部分，于是考虑显式地描述状态：f(i,S_1,S_2,X,Y)，其中 i 表示当前处理到的点的下标，S_1 和 S_2 分别表示与当前结点在一棵树中的前者/后者所有点的集合（与当前点不连通的点），X 表示已经划分出来的子集的数目，Y 表示在 [X+1,t] 中的第一个还没有被计算的子集的下标。我们可以将点按照 DFS 序排列，这样对于每个点 i，我们可以通过 i 的 DFS 子树所有节点的位置区间来确定他所属的集合（左半部分和右半部分之一）。因此，严格来讲，我们的状态中还可以增加一个参数，表示当前处理的状态对应的结点集合大小之和，以保证每个集合都不超过 k。

考虑如何计算 f。我们显然需要递归地计算出 f(i-1,S_1',S_2',X',Y')。于是枚举与 i 相邻的点 j，此时有两种情况：

这个操作描述地比较麻烦，实际上可以看做是从 V_X 中新增了一个点，其它点继续沿用之前的划分方案即可。因此，我们对答案贡献的统计就没有必要按照式子计算了，只需要记录下最小值即可，在递归返回时进行合并。最后将整张图二分即可。

代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int n, m, f[N][30], cnt, size[N], flag[N];
vector<int> g[N], c[N];
struct node {
    int u, v, nxt;
} e[N << 1];
void ad(int u, int v) {
    e[++cnt].u = u; e[cnt].v = v; e[cnt].nxt = flag[u]; flag[u] = cnt;
    e[++cnt].u = v; e[cnt].v = u; e[cnt].nxt = flag[v]; flag[v] = cnt;
}
int deep[N], st[N], ed[N], top, T;
void dfs1(int u, int fa) {
    size[u] = 1;
    for (int i = 0; i < g[u].size(); i++) {
        int to = g[u][i];
        if (to == fa) continue;
        deep[to] = deep[u] + 1;
        dfs1(to, u);
        size[u] += size[to];
    }
}
void dfs2(int u, int fa, int dis) {
    if (dis > size[u]) return ; 
    if (st[deep[u]] == 0) st[deep[u]] = u; 
    ed[deep[u]] = u;
    if (dis == size[u]) {
        for (int i = deep[u]; i >= 1; i--) {
            int x = st[i], y = ed[i];
            c[x].push_back(y); c[y].push_back(x); 
        }
        return ;
    } else if (dis < size[u]) {
        int to = -1;
        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            if (v == fa) continue;
            if (size[v] > size[to]) to = v;
        }
        dfs2(to, u, dis + size[to]);
        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            if (v == fa || v == to) continue;
            dfs2(v, u, size[v]);
        }
    }
}
void dfs(int u) {
    for (int i = 1; i <= 20; i++) {
        f[u][i] = f[f[u][i - 1]][i - 1];
    }
    for (int i = 0; i < c[u].size(); i++) {
        int to = c[u][i];
        if (to == f[u][0]) continue;
        f[to][0] = u; dfs(to);
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int u, v; scanf("%d%d", &u, &v);
        ad(u, v);
    }
    deep[1] = 1; dfs1(1, 0);
    dfs2(1, 0, 1);
    for (int i = 1; i <= n; i++) {
        sort(c[i].begin(), c[i].end(), [](int a, int b){return size[a] < size[b];});
        if (c[i].size() > 0 && size[c[i][0]] >= size[i] * 2) {
            c[i].erase(c[i].begin());
        }
    }
    dfs(1);
    int k;
    for (k = 1; k <= n; k++) {
        bool flag = 1;
        for (int i = 1; i <= n; i++) {
            if (size[i] > k) {
                int u = i;
                for (int j = 20; j >= 0; j--) {
                    if (f[u][j] != 0 && size[f[u][j]] <= k) {
                        u = f[u][j];
                    }
                }
                if (flag && !c[u].empty()) {
                    flag = 0; 
                    for (int l = 0; l < c[u].size(); l++) {
                        if (size[c[u][l]] <= k) continue;
                        int v = c[u][l];
                        printf("%d ", 2);
                        printf("%d ", size(u)); 
                        while (u != f[v][0]) printf("%d ", u), u = f[u][0]; 
                        printf("%d\n", u);
                        printf("%d ", size(v));
                        while (v != f[u][0]) printf("%d ", v), v = f[v][0];
                        printf("%d\n", v);
                        break;
                    }
                } else {
                    printf("%d ", 1);
                    printf("%d ", size(i));
                    while (size(u) < k) u = f[u][0];
                    while (size(i) > k) {
                        printf("%d ", i); i = f[i][0];
                    }
                    printf("%d\n", u);
                }
            }
        }
        if (!flag) break;
    }   
    printf("%d %d\n", k, cnt );
    return 0;
}