[SCOI2005]王室联邦|树分块

薯粉块……真香!

P2325 [SCOI2005]王室联邦

题目描述

“余”人国的国王想重新编制他的国家。他想把他的国家划分成若干个省,每个省都由他们王室联邦的一个成员来管理。

他的国家有n个城市,编号为1..n。一些城市之间有道路相连,任意两个不同的城市之间有且仅有一条直接或间接的道路。为了防止管理太过分散,每个省至少要有B个城市,为了能有效的管理,每个省最多只有3B个城市。

每个省必须有一个省会,这个省会可以位于省内,也可以在该省外。但是该省的任意一个城市到达省会所经过的道路上的城市(除了最后一个城市,即该省省会)都必须属于该省。

一个城市可以作为多个省的省会。

聪明的你快帮帮这个国王吧!

输入输出格式

输入格式:

第一行包含两个数N,B(1<=N<=1000, 1 <= B <= N)。接下来N-1行,每行描述一条边,包含两个数,即这条边连接的两个城市的编号。

输出格式:

如果无法满足国王的要求,输出0。否则第一行输出数K,表示你给出的划分方案中省的个数,编号为1..K。第二行输出N个数,第I个数表示编号为I的城市属于的省的编号,第三行输出K个数,表示这K个省的省会的城市编号,如果有多种方案,你可以输出任意一种。

输入输出样例

输入样例#1:

1
2
3
4
5
6
7
8
8 2 
1 2
2 3
1 8
8 7
8 6
4 6
6 5

输出样例#1:

1
2
3
3 
2 1 1 3 3 3 3 2
2 1 8

转化一下题意就是,给你一颗多叉树,让你输出一种划分方案,使得每块大小不小于B又不超过3B。

读完题之后还是不明所以……这不是随便分一分就好了吗……

怎么分?dfs每找到B个就分一块……恩好像不太对,这样连通性无法保证啊。比如说,我们现在在一个节点的左子树中搜(假设它是一棵二叉树)。这个左子树还没搜完就达到B个了,按照刚才的想法,我们把它划成一块;但是继续往下搜,直到搜完这棵左子树的剩余部分,还是没有达到B个。这时根据Dfs我们肯定会向右子树中去找剩下的点。好了。你左子树中已经搜了一部分了,也就是说你第二次搜到的点很可能已经和根节点不连通了,既然和根节点都不联通了,更不要说右子树了。

那怎么办呢?

显然上述情况的错误是因为访问顺序的缘故。那我们能不能从底部往上组块呢?当然可以辣!这样显然是保证了连通性的。

由此我们得到了一个算法:首先我们需要一个栈,假设我们现在Dfs到了x,第一次访问它时,栈的栈顶作为相对栈底,每遍历完它一个子节点所在的子树,判断一下此时栈顶到相对栈底的元素个数是不是大于等于B。若成立,那么栈顶弹至相对栈底,这些弹出的点组成一个块,根为省会。当访问完所有子节点要回溯到x的父节点时,我们把x压入栈。显然这样规定省会省会只在另==一==个块中,而不会被第二个块抢走。这个东西就是薯粉块树分块

这样为什么就可以解决上面的问题呢?比如说我现在有一个根节点,他的左子树是一个节点,他的右子树是一条很长很长的链。那么显然这时普通Dfs无法保证右子树最后的几个不超过B的点与左子树联通。那么改进后的算法呢?它不是每次遍历完这个子树才判断栈里元素的吗?那它的右子树如果节点数超过了3B,是不是就会形成一个超过3B的大块呢?

没有这个疑问的同学,思路比较清晰。有这个疑问的同学,可能对Dfs的过程还不是很清楚。注意到栈底是相对栈底,只要每次访问到一个节点,对于这个节点都会有一个相对栈底。显然到了右子树时,栈中的元素先暂时被“忽略了”,因为这时的相对栈底已经变成了右子树的根节点。所以我们的流程跟准确的说其实是,从下自上(Dfs回溯),如果该节点的相对栈底到栈顶的元素个数不足B,那么”舍弃“这个栈底,将该节点入栈,然后再对新的相对栈底判断。所以分块的情况是:每棵子树较深的部分自己组块,若子树有剩余的,在靠近根的地方组成一个大块。显然,每个子树中剩余的最多只有B个,由于我们的策略是大于B就分一个块,所以每个块一定小于2B。如果全加起来也不够B,就到根的父亲节点再去找。因为这些节点即使不够B,但他们仍在栈中,仍“优先考虑”他们组块。

最后结束时栈中还会有剩余没有组成块的节点,但这些节点显然一定是联通的。那么他们的个数就一定小于B。而且仔细思考一下我们会发现,这些点与最后一个划分出来的块显然也是联通的。划分出的块的大小一定小于2B。那么我们就可以把它们合成一个大块,这个块的大小不超过3B。

我是不是太啰嗦了

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <cstring>
#include <cstdlib>
#include <cfloat>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cctype>
#include <map>
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 1010;
int N, B;
int root[MAXN], bel[MAXN], st[MAXN], cnt, top;

struct Edge {
int to, nxt;
}e[MAXN << 1];

template <typename _Tp>
inline void read(_Tp &x) {
char ch = getchar( ); bool f = 0; x = 0;
while (!isdigit(ch)) { if (ch == '-') f = 1; ch = getchar( ); }
while (isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar( ); }
x = f ? -x : x;
}

int head[MAXN], tot;
void AddEdge(int x, int y) {
e[++ tot].to = y, e[tot].nxt = head[x], head[x] = tot;
}

void Dfs(int x, int fa) {
int now = top;
for (int i = head[x], v; i; i = e[i].nxt) {
v = e[i].to;
if (v == fa) continue;
Dfs(v, x);
if (top - now >= B) {
root[++ cnt] = x;
while (top != now) bel[st[top --]] = cnt;
}
}
st[++ top] = x;
}

int main( ) {
read(N), read(B);
int x, y;
for (int i = 1; i < N; ++ i) {
read(x), read(y);
AddEdge(x, y);
AddEdge(y, x);
}
Dfs(1, 0);
while (top) bel[st[top --]] = cnt;
printf("%d\n", cnt);
for (int i = 1; i <= N; ++ i) printf("%d ", bel[i]);
printf("\n");
for (int i = 1; i <= cnt; ++ i) printf("%d ", root[i]);
printf("\n");
return 0;
}

然鹅,虽然A掉了这道题,但在luogu题解评论区中看到了一组hack数据:2 2 1 2

???

对啊……为啥我的程序会输出0啊……

手动模拟一下我们会发现,只让省会在另一块中的话,显然省会只能在当前块中的情况就没法考虑了啊……(我是还以为这种情况都能转化成省会在另一块的情况呢……QWQ)那咋办?

在参考了没有被hack的hzwer神犇的代码后……

应该没有问题的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<iostream>
#include<cstdio>
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,B,cnt,top,pro;
int last[1005],q[1005],size[1005],cap[1005],belong[1005];
struct data{int to,next;}e[2005];
void insert(int u,int v)
{
e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;
e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;
}
void dfs(int x,int fa)
{
q[++top]=x;
for(int i=last[x];i;i=e[i].next)
if(e[i].to!=fa)
{
dfs(e[i].to,x);
if(size[x]+size[e[i].to]>=B)
{
size[x]=0;
cap[++pro]=x;
while(q[top]!=x)
belong[q[top--]]=pro;
}
else size[x]+=size[e[i].to];
}
size[x]++;
}
void paint(int x,int fa,int c)
{
if(belong[x])c=belong[x];
else belong[x]=c;
for(int i=last[x];i;i=e[i].next)
if(e[i].to!=fa)
paint(e[i].to,x,c);
}
int main()
{
n=read();B=read();
if(n<B){puts("0");return 0;}
for(int i=1;i<n;i++)
{
int u=read(),v=read();
insert(u,v);
}
dfs(1,0);
if(!pro)cap[++pro]=1;
paint(1,0,pro);
printf("%d\n",pro);
for(int i=1;i<=n;i++)printf("%d ",belong[i]);
printf("\n");
for(int i=1;i<=pro;i++)printf("%d ",cap[i]);
printf("\n");
return 0;
}

我们发现:

hzwer神犇在一开始就把x压到了栈里?然后对于每个点维护一个siz表示x所在块中以x为根的子树大小。注意如果这个节点第一次访问,那么他的siz是不包括当前节点的,如果加起来大于等于B,那么就是说没有省会的情况块也大于等于B,那么省会就分到别的块里去(siz[x]=0)。

考虑刚才省会只能在块里的情况……似乎……Dfs里也没解决啊!(メ`ロ´)/

不过显然1,2还是存在了栈中。两份代码应该在处理剩余节点的地方有所不同。那么看看第一份代码,是将栈里的每个元素都赋值成了……cnt?!天啊恍然大悟!cnt在第一份代码里一直是0啊!但是显然块中元素应该在一个块里啊!那加上if (!cnt) cnt++;!

这时输出了1 1 1 0。对了,我们还有一个首都问题没有解决。这组数据中显然随便选一个首都就行,但是其他数据中呢?仔细分析可知,只可能在N=B时省会只能在块里,否则把它塞到上一个块里面就好了。所以这时省会为1一定没错。

第一份代码计算belong前加上

1
if (!cnt) root[++ cnt] = 1;

就行了。

不知道为什么关于树分块网上的代码要么讲解很少要么就是错的……蒟蒻我理解了很久才明白QWQ

最后……怎么说呢……我很庆幸我不是那个拿着一份错误代码将错误进行到底的人

QWQ溜了溜了

所以说离NOIP只有10多天了我还在这里学奇奇怪怪的东西……不学了不学了,还是多做做NOIP范围内的题巩固一下基础叭

OvO

{% if theme.fireworks %} {% endif %} {{ live2d() }}