[eJOI2018]互素树

Kubic · 2021-05-11 11:10:48 · 题解

这是一篇直接交代码就能过的题解

虽然我不会证明任何东西，但是它就是跑得快！！1

具体做法：

发现 2 的倍数非常多，占到了一半，先考虑将这棵树二分图染色。

容易发现黑白两色中至少有一种颜色个数超过一半，那么从这种颜色中随机选出一些按顺序填上 2 的倍数。

然后将剩下的数 random_shuffle 一下，相当于随机顺序，按照这个顺序依次找到编号最小的能够填它的位置并填上。

如果不放心可以把编号也 random_shuffle 一下，不过我没这么做。

找到解的概率完全不会算，但是跑的飞快，300ms 不到就过了。

有一些优化方法可能可以跑得更快，但是可能会使代码不能看。

• 尽量将大质数填在度数大的节点上。

• 将更多小质数的倍数预先填上去，而不只是 2 的倍数。

• random_shuffle 似乎不是均匀随机（?）可以手写一个出来。

• 交之前洗把脸。

代码：

#include <bits/stdc++.h>
using namespace std;
#define N 100005
#define pb push_back 
#define set(a,vl) memset(a,vl,sizeof(a))
int T,n,ord[N],a[N];bool col[N];set<int> z;
vector<int> vc1[2],e[N];
int gcd(int x,int y) {return y?gcd(y,x%y):x;}
void dfs(int u,int f)
{
    col[u]=col[f]^1;vc1[col[u]].pb(u);
    for(int i=0,v;i<e[u].size();++i)
    {v=e[u][i];if(v!=f) dfs(v,u);}
}
bool chk(int u,int x)
{
    for(int i=0,v;i<e[u].size();++i)
    {v=e[u][i];if(a[v] && gcd(x,a[v])>1) return 0;}return 1;
}
void upd(int u,int x) {a[u]=x;z.erase(u);}
bool slv1()
{
    ord[0]=0;set(a,0);z.clear();
    random_shuffle(vc1[0].begin(),vc1[0].end());
    for(int i=2;i<=n;i+=2) a[vc1[0][i/2-1]]=i;
    for(int i=1;i<=n;i+=2) ord[++ord[0]]=i; 
    random_shuffle(ord+1,ord+ord[0]+1);
    for(int i=1;i<=n;++i) if(!a[i]) z.insert(i); 
    for(int i=1,j;i<=ord[0];++i)
    {
        bool fl=0;
        for(set<int>::iterator it=z.begin();it!=z.end();++it)
        {j=*it;if(chk(j,ord[i])) {upd(j,ord[i]);fl=1;break;}}
        if(!fl) return 0;
    }return 1;
}
void slv()
{
    scanf("%d",&n);vc1[0].clear();vc1[1].clear();
    for(int i=1;i<=n;++i) e[i].clear();
    for(int i=1,u,v;i<n;++i)
        scanf("%d %d",&u,&v),e[u].pb(v),e[v].pb(u);dfs(1,0);
    if(vc1[0].size()<vc1[1].size()) swap(vc1[0],vc1[1]);
    while(1) if(slv1()) break;
    for(int i=1;i<=n;++i) printf("%d ",a[i]);puts("");
}
int main()
{
    srand(time(0));
    scanf("%d",&T);while(T--) slv();return 0;
}