自动搬运

查看原文

来自洛谷，原作者为

	Froggy 最初的一步，泪水之后再一次，雕刻的风景线，消逝在黄昏中的风，直到梦的最后。—— Clannad

搬运于2025-08-24 22:07:02，当前版本为作者最后更新于2020-06-09 20:13:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

注：此做法亦可通过 加强版。并且在加强版中表现得更加优秀。

（为了水估值，我也会把这个做法发到加强版中）

既然是个提答，通常不会有什么复杂度正经的做法，多半是考验乱搞能力。

（不过这题好像 xtq 等大佬交了 cpp 文件就跑过去了，我不得不%%%。）

核心思想：随机化 + 贪心

随机化：

随机出来一个排列，即把每个要填的数随出来个优先级，优先级较高的优先考虑。

直接每次 random_shuffle 即可。

贪心：

从根（可以自己规定，也可以随机）出发，dfs 一遍树，每个节点填入剩下的数中与父亲节点互质且优先级最高的数。

用 set 维护剩余的数即可。

根据以上两条就足以通过此题了 ^_^ 。

我就放下代码吧。

code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
#define N 100010
int T,n,x[N],y[N],p[N],ans[N],mn,tot,tmp[N];
set<int> s;
inline int _gcd(int a,int b){
	if(b==0)return a;
	return _gcd(b,a%b);
}
vector<int> G[N];
void dfs(int u,int fa){
	for(auto i:s){
		if(!fa||_gcd(tmp[fa],p[i])==1){
			tmp[u]=p[i],s.erase(s.find(i));
			break;
		}
	}
	if(!tmp[u]){
		++tot;
		tmp[u]=p[(*s.begin())];
		s.erase(s.begin());
	}
	for(auto v:G[u]){
		if(v==fa)continue;
		dfs(v,u);
	}
}
int main(){
	freopen("x.in","r",stdin);
	freopen("x.out","w",stdout);
	T=read();
	while(T--){
		n=read();
		for(int i=1;i<=n;++i)G[i].clear(),p[i]=i;
		for(int i=1;i<n;++i){
			int u=read(),v=read();
			G[u].push_back(v),G[v].push_back(u);
		}
		mn=n;
		for(int Test=1;;++Test){
			s.clear();
			random_shuffle(p+1,p+n+1);
			for(int i=1;i<=n;++i)tmp[i]=0,s.insert(i);
			tot=0;
			dfs(1,0);
			if(tot<mn){
				mn=tot;
				for(int i=1;i<=n;++i){
					ans[i]=tmp[i];
				}
			}
			if(!mn)break;
		}
		for(int i=1;i<=n;++i){
			printf("%d ",ans[i]);
		}
		printf("\n");
	}
	return 0;
}

如果没有耐心，那么随便跑跑即可获得 $95+$ 的高分。（测试点 $1\sim 6$ 可以秒出。）

如果有一点耐心，用不到 $30min$ 即可得到 $100$ 分。

在加强版中就更加优秀了，最后一个点不到 $1min$ 就跑完了。有图为证：

因为是个提答，并且我比较懒，所以到这里我就结束了。

其实还有非常多可以优化的地方。（其实这种题目就是仁者见仁，智者见智嘛。）

举个例子吧：把节点按度数排序，度数大的放上大质数。

当然，做完后也不妨思考一下有木有多项式复杂度的解法。

Froggy's blog

呱!!