题解：CF2040D Non Prime Tree

· · 题解

CF992Div2 D-solution

给定一个 n 个节点的树，你可以不重复地给树的节点填 1\sim 2n 之间的数，求一种构造方案，使得每两个相邻的节点上的数之差的绝对值为合数。

我们规定每次填的数只会变大（就是在以某种方法遍历的时候后面的数一定比前面的数大）。现在我们假设填到了 u 节点，u 节点填的数是 val_u，u 的儿子为 v_0,v_1,v_2,\dots，其中 v_0 是长儿子任意一个儿子。

现在我们归纳证明，如果每个 v 子树内最大的数小于 val_v+siz_v\times 2 -1，则存在一种构造方案，使得 u 子树内最大的数小于 val_u+siz_u\times 2-1。这样做下去根节点 1 的子树内最大的数小于 n\times 2，满足题意。

如果 siz_u=1，即 u 没有儿子，显然满足条件。

我们填 val_{v_0}=val_{u}+1，下一个子树还能填的数是 x=val_{v_0}+siz_{v_0}\times 2-1=val_{u}+siz_{v_0}\times 2

  1. 如果 siz_{v_0}\neq 1。

    显然 x-val_u=siz_{v_0}\times 2 是一个合数，我们直接填 val_{v_1}=x。则填完后还能从 x'=val_{v_1}+siz_{v_1}\times 2-1 =val_u+(siz_{v_0}+siz_{v_1})\times 2-1 填下一个子树，我们填 val_{v_2}=x'+1 即可满足合数条件。执行这样的操作，我们可以保证填完所有子树后，还能填的数是 val_u+\sum siz_v\times 2-1<val_u+siz_u\times 2-1，成立。

  2. 如果 siz_{v_0}=1。

    • 如果 siz_u=2，即 u 只有这一个子树，显然 val_u+1<val_u+siz_u\times 2-1。

    • 否则填 val_{v_1}=val_u+4，那么接下来能填的数 x'=val_u+4+siz_{v_1}\times 2-1=val_u+(siz_{v_0}+siz_{v_1})\times 2+1，于是我们填 val_{v_2}=x’+1 即可满足合数条件。执行这样的操作，我们可以保证填完所有子树后，还能填的数是 val_{u}+\sum siz_v \times 2+1=val_u+siz_u\times 2-1，成立。

于是就得证了。

所以只要一个 val_v=val_u+1，剩下的 u 的儿子找一个最小的 k>1，填 val_u+2k 大于目前已填的数即可。

我写代码的时候是用长链填连续的数写的，稍微麻烦一点。主要还是证明要严格比较费脑子。

下面的代码是上面的做法。

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int>ttfa;
typedef long long ll;

const int N=200005;
int Test;
int n,tot=0,ans[N];

vector<int>tar[N];

void dfs(int u,int f){
    bool flag=0;
    ans[u]=++tot;
    for(auto v:tar[u]){
        if(v==f)continue;
        if(!flag){
            dfs(v,u);
            flag=1;
            continue;
        }
        if(tot+1-ans[u]==2)tot=ans[u]+3;
        else if((tot+1-ans[u])%2==1)++tot;
        dfs(v,u);
    }
}

int main(){
    scanf("%d",&Test);
    while(Test--){
        scanf("%d",&n);tot=0;
        for(int i=1;i<=n;++i)
            tar[i].clear();
        for(int i=1;i<n;++i){
            int u,v;scanf("%d%d",&u,&v);
            tar[u].push_back(v);
            tar[v].push_back(u);
        }
        dfs(1,0);
        for(int i=1;i<=n;++i)
            printf("%d ",ans[i]);
        puts("");
    }
    return 0;
}