题解

思路

操作会把最初的每条边复制成平移后的另一条边，因此最终边数一定是偶数；树有 $N-1$ 条边，所以 $N$ 为偶数时无解。

做法

若 $N$ 为奇数，令 $g=\gcd(N,K)$、$h=N/g$，把顶点排成 $h$ 行 $g$ 列，第 $r$ 行第 $c$ 列放置 $(rK\bmod N)+c$。平移 $K$ 恰好使每个顶点移动到同一列的下一行，且 $g,h$ 都是奇数。

在偶数编号列中，每隔一行加入一条竖边；在偶数编号列与右侧列之间，同样每隔一行加入一条横边；在奇数编号列与右侧列之间，只在倒数第二行加入一条横边。所有这些边平移后恰好补上相邻的下一行：每个偶数列形成一条纵向主链，其右侧奇数列的顶点依次作为支点接入，再由底部两条边连接到下一条主链，因此所得图连通且无环，边数为 $N-1$。

复杂度

构造时间和额外空间均为 $O(N)$。