主要是为了奶一下两位 神

luogu 2325 王室联邦

S1

这道题其实是很尬的。
刚看到这道题的时候第一个想法就是搜，但怎么搜是个问题。第一个想法是枚举子树，之后针对每个子树单独处理，但是想了一会之后发现不好实现。第二个想法是每B个确定一个省，然后最后剩下的归到已经确定好的省里面。这个后来被证实是正解。
比较尬，最后我用的这两个方法结合起来做的。

S2

一开始我就是按照我的第二个想法不加任何修饰地做的，先广搜确定层数，之后从下往上搜B个，是一个省，搜不够就归到旁边的省里面。这个想法其实漏洞百出，特别呲，但是由于SPJ牛逼所以莫名其妙的了80分。
可以被和这组类似的数据卡掉（这组本身并不能）

13 4    
1 2    
1 3    
3 4    
4 5    
2 6    
6 7    
7 8    
2 9     
9 10    
9 11    
9 12    
9 13

这种数据的特点是一条链，我的dfs会一路选上去，但是这条链上面的子树都不到B个，最后只能都归到一个省里面，就会GG。实际上应该把这条链一分两半地选。

S3

针对这种数据，我想起了我的第一个方法，于是我加了一个结构体，然后在广搜的时候单向加边，每搜到一个点，看看它的子树里面没有搜过的够不够B个，最后再单独处理不能组成一个省的城市群。
最后剩下的每一个城市群子树有一个特点，它的根节点的父节点一定被选过（不然就会先枚举它的父节点了），它的所有子孙节点都没有选过。这样可以克服刚才的问题。那么把这个城市群加到根节点的父节点的省里面就可以了。
但是还有一点就是1节点的处理，因为它没有父节点。这也好办，最后一个省肯定是距离1节点最近的一个，所以可以把1节点的城市群加入到最后一个省里面。
然而这样只有90分。
这就很绝望了，我又想了半个小时才想出怎么回事。
可以用这组数据卡掉

16 4
1 2    
1 3    
1 4    
1 5    
2 6
2 7
2 8
2 9
2 10
6 11
7 12
8 13
9 14
10 15
13 16

这种数据有一个特点，就是以某个节点作为根节点，它的所有子节点为根的子树代表的城市群都不超过B个城市，但是加起来就能超过3B个城市。
一开始我以为这种数据根本就不可能存在，但是事实证明我错了。

S4

这种数据当然存在，因为题目里面存在这样一句话：
“一个城市可以作为多个省的省会。”
这里就产生了一个歧义问题，还好被asia大佬解决了。这个省会到底算作哪个省的呢？答案是，只能算作一个省的，而剩下几个省必须做到出了这个省会有B个城市才行。
解决这个问题倒也简单，针对一个点为根节点的城市群用while进行多次搜索，只要能搜到B个就继续搜，这样就能保证绝对正确了。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#define rint register int 
#define inv inline void
#define mc(a,i,x,y,z) for (i=x;i<=y;i++) a[i]=z;
using namespace std;
int cnt,b,h,t,num,n,hh,lst;
int ans[1001],ca[1001],q[1001],team[1001],head[2001],hed[2001],fa[1001];
bool vis[1001],flag;
struct node
{
	int next,to;
}ljb[2001],edg[2001];
inv add(int x,int y)
{
	edg[++cnt].next=hed[x];
	edg[cnt].to=y;
	hed[x]=cnt;
}
inv adn(int x,int y)
{
	ljb[++cnt].next=head[x];
	ljb[cnt].to=y;
	head[x]=cnt;
}
inv bfs()
{
	h=0;t=1;team[1]=1;vis[1]=1;
	while (h<t)
	{
		int x=team[++h];
		for (rint i=hed[x];i;i=edg[i].next)
		{
			int y=edg[i].to;
			if (!vis[y])
			{
				vis[y]=1;
				team[++t]=y;
				fa[y]=x;
				adn(x,y);
			}
		}
	}
}
inv dfs(int x)
{
	q[++cnt]=x;vis[x]=1;
	if (cnt==b) return;
	for (rint i=head[x];i;i=ljb[i].next)
	{
		int y=ljb[i].to;
		if (!vis[y]) dfs(y);
		if (cnt==b) return;
	} 
}
inv color(int x,int c)
{
	ans[x]=c;
	for (rint i=head[x];i;i=ljb[i].next)
	{
		int y=ljb[i].to;
		if (!vis[y]) color(y,c);
	} 
}
int main()
{
	scanf("%d%d",&n,&b);
	for (rint i=1;i<=n-1;i++) 
	{
		int x,y;scanf("%d%d",&x,&y);
		add(x,y);add(y,x);
	}
	cnt=0;bfs();
	mc(vis,hh,1,n,0);
	for (rint i=t;i>=1;i--)
		if (!vis[team[i]])
		{
			cnt=0;mc(q,hh,1,n,0);
			dfs(team[i]);
		    while (cnt==b)
			{
				num++;
				for (rint j=1;j<=cnt;j++) ans[q[j]]=num;
				ca[num]=team[i];
				cnt=-1;
				mc(q,hh,1,n,0);
				dfs(team[i]);
			}
			for (rint j=1;j<=cnt;j++) vis[q[j]]=0;
		}
	if (!vis[1]) color(1,num);
	for (rint i=2;i<=t;i++)
		if (!vis[team[i]]) 
			color(team[i],ans[fa[team[i]]]);
	printf("%d\n",num);
	for (rint i=1;i<=n;i++) printf("%d ",ans[i]);
	printf("\n");
	for (rint i=1;i<=num;i++) printf("%d ",ca[i]);	
}

总结

  1. 一定不能看题解，有耐心地做题，能做出来就是好的。
  2. 多考虑从几种情况，但是一定要证明这种情况的存在性。考试的时候不能评测多次。
  3. 仔细读题，特别是看起来很关键的话。想想针对题目里的这句话可以怎么做。当然也不能被题目卡死，参考【打鼹鼠】这道题。

    PS

    在这里，我必须膜拜一下ASIA和ZYC两位

    神

    一开始我想出解法的时候，讲给了两位

    神

    然而

    神

    表示：这还用你说？并以堪比

    光速

    的速度打出了简短的代码。正在我冥思苦想的时候，

    神

    已经

    轻松
    一遍
    AC

    了这道题 然后

    神

    对我说：这题难度

    虚高

    了吧。SB的我说这题有难度啊。

    神

    轻蔑地
    冷笑

    并说道：我的代码长度是你的

    一半

    而且A掉的时间也是你的

    一半

    并说出了真正的正解：只需要一遍DFS，搜到底之后往上回溯，记录编号，回溯的时候够了B个就归到一个省。这样的思路和我的大体思想一致，然而不知道比我高到哪里去了。
    放上

    神

    的代码

    #include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define re register
#define maxn 1000007
#define ll long long
using namespace std;
struct po
{
int to,from,nxt;
};
po edge[10001];
int head[10001],n,m,B,b[100001],ans,t,rt[1001],fa,cnt,srk[1001],num,s;
inline void add_edge(int from,int to)
{
edge[++num].nxt=head[from];
edge[num].to=to;
head[from]=num;
}
inline void dfs(int u,int f)
{
int q=fa;
for(re int i=head[u];i;i=edge[i].nxt)
{
    if(edge[i].to==f)
    continue;
    dfs(edge[i].to,u);
    if(fa-q>=B)
    {
        cnt++;
        rt[cnt]=u;
        while(fa>q)
        {
            b[srk[fa--]]=cnt;
        }
    }
}
srk[++fa]=u;
}
int main()
{
cin>>n>>B;
for(re int i=1;i<=n-1;i++)
{
    cin>>s>>t;
    add_edge(s,t);
    add_edge(t,s);
}
dfs(1,0);
while(fa)
{
    b[srk[fa--]]=cnt;
}
cout<<cnt<<endl;
for(re int i=1;i<=n;i++)
cout<<b[i]<<" ";
cout<<endl;
for(re int i=1;i<=cnt;i++)
{
    cout<<rt[i]<<" ";
}
return 0;
}

    ASIA和ZYC果然不愧于

    神

    的称号。

    神

    在我心中的形象又高大了许多。
    谨以此题
    表达我对

    神

    深深的

    膜意

赞 赏
蒟蒻的邮箱:xmzl200201@126.com