题解：CF2040D Non Prime Tree

naromil · 2024-12-15 10:54:44 · 题解

CF2040D Non Prime Tree

如果相邻的点之间的绝对值差必须为非质数，我们不难想到 2 以外的偶数和 1，结合所有权值不能超过 2n，于是我们有个初步的想法就是为每个点赋值每个偶数，然后找到一个顺序使得没有相邻的点连着赋值。

那么我们就可以先将点按深度分类，然后不难发现如果总深度 \ge 5，就可以先遍历每个奇数深度行，然后遍历每个偶数深度行，对每行的所有点依次赋值每个偶数，然后就解决了。如果总深度 =1，答案直接输出 1 即可。

对于剩下的深度，我们发现无论怎么遍历都会有两行相邻。于是我们不难想到可以将一个叶子作为根，然后 1，2 行就都将只有一个点了。然后我们就可以对总深度分类讨论，解决剩下的深度。

• 树深度 =2，先对 1，2 层依次赋偶数。
• 树深度 =3，先对 3，1，2 层依次赋偶数。
• 树深度 =4，先对 4，2，1，3 层依次赋偶数。

然后由于 1，2 层各只有一个点，且它们差值为 2，我们直接将根节点 + 1 或 - 1，使得差值为 1，就解决了。

#include<bits/stdc++.h>
#define emp emplace_back
using namespace std;
using ll=long long;
const int kn=2e5+25;
int n,dep[kn],a[kn],rot,maxdep;
vector<int> c[kn];
void dfs(int u,int b){
    rot=u;
    dep[u]=dep[b]+1;
    for(auto v: c[u]){
        if(b==v) continue;
        dfs(v,u);
    }
}
vector<int> fl[kn];
inline void _solv(){
    cin>>n;
    maxdep=rot=0;
    for(int i=1;i<=n;++i){ c[i].clear(); fl[i].clear(); }
    for(int i=2,x,y;i<=n;++i){ cin>>x>>y; c[x].emp(y); c[y].emp(x); }
    dfs(1,0); dfs(rot,0);
    for(int i=1;i<=n;++i){ fl[dep[i]].emp(i); maxdep=max(maxdep,dep[i]); }
    int cnt=0;
    if(maxdep==1){ printf("1\n"); return; }
    else if(maxdep==2){ printf("1 2\n"); return; }
    else if(maxdep==3){
        for(auto cr: fl[3]) a[cr]=(cnt+=2);
        a[fl[1][0]]=(cnt+=3);
        cnt=a[fl[2][0]]=++cnt;
    }
    else if(maxdep==4){
        for(auto cr: fl[4]) a[cr]=(cnt+=2);
        a[fl[2][0]]=(cnt+=2);
        a[fl[1][0]]=(cnt+=1);
        ++cnt;
        for(auto cr: fl[3]) a[cr]=(cnt+=2);
    }
    else{
        for(int i=1;i<=maxdep;i+=2) for(auto cr: fl[i]) a[cr]=(cnt+=2);
        for(int i=2;i<=maxdep;i+=2) for(auto cr: fl[i]) a[cr]=(cnt+=2);
    }
    for(int i=1;i<=n;++i){ printf("%d ",a[i]); }
    printf("\n");
}
signed main(){
    cin.tie(0)->ios::sync_with_stdio(false);
    int T; cin>>T;
    while(T--) _solv();
    return 0;
}