这是一道 CF 2040D - Non Prime Tree 的构造题。
下面给出详细题解。

题目大意

给定一棵 $n$ 个节点的树。
需要给每个节点 $i$ 赋值 $a_i$，满足：

• $a_1, a_2, \dots, a_n$ 是 $1$ 到 $2n$ 的 排列（即互不相同）
• 对每条边 $(u, v)$，$|a_u - a_v|$ 不是质数

求任意一组解，或输出 $-1$ 表示无解。

关键结论

1. 一定存在解（对于任意树，本题不会输出 $-1$）。
2. 构造方法很多，这里采用 DFS + 贪心调整。

标程算法分析

核心思路

• 以 $0$ 号节点为根，进行 DFS。
• 给根节点赋值为 $1$。
• 在 DFS 过程中，给每个子节点分配一个 严格递增 的整数。
• 保证相邻节点的差值 不是质数，且差值最好是 偶数（除了 $2$，因为 $2$ 是质数）。

具体步骤

设当前节点为 $v$，值为 res[v]，要为其子节点 to 赋一个值 res[to]：

1. 初始令 res[to] = lst + 1，其中 lst 是上一个已赋值的数。

2. 如果 res[to] 不满足以下条件，则不断 res[to]++：

   • res[to] != res[v] + 1（避免差为 $1$，$1$ 不是质数，这里主要是为了允许其他调整）
   • 且 (res[to] % 2 != res[v] % 2 || res[to] - res[v] == 2)
     这个条件的意思是：
     如果 res[to] 与 res[v] 奇偶性相同（差为偶数），那么不能差为 $2$（因为 $2$ 是质数）。
     如果奇偶性不同，差为奇数，奇数可以不是质数吗？奇数可能是质数（如 $3,5,7$）。
     因此这个判断实际是：尽量让差是 偶数且不等于 2。

3. 赋值后更新 lst = res[to]。

4. 递归处理 to 的子节点。

为什么这样可行？

• 每次给子节点赋的值是当前未用过且尽量大的数（递增）。
• 通过 while 循环跳过差的绝对值为质数的情况。
• 因为 $1$ 到 $2n$ 的范围足够大（$n$ 个节点，$2n$ 个数总能找到递增方案）。
• 该构造保证每个数只用一次，且差值满足条件。

复杂度

• 每个节点赋值最多调整 $O(1)$ 次（因为增量的间隔不会太大）
• DFS 遍历 $O(n)$
• 总复杂度 $O(n)$ 每个测试用例
• 总 $n$ 和 $\le 2\cdot 10^5$，可通过

总结

• 本题存在构造解，不会输出 $-1$。
• 标程使用 DFS + 贪心递增赋值，并通过奇偶性和差值判断跳过质数差。
• 因数字范围 $1$ 到 $2n$ 足够，总能找到不冲突的赋值。