题解：P15568 [COCI 2025/2026 #5] 摆放 / Slaganje

· · 题解

讲一个简单确定性做法。

考虑到这是构造题，直接猜测最终构造形如一棵树的所有编号轮换。

定义一条边 (x,y) 的距离为 \min(|x-y|,n-|x-y|)，那么需要给原树编号使得 1\sim\lfloor\frac{n}{2}\rfloor=m 这些距离均出现过。

原树限制过多，但我们只需要 m 条边。注意到一个比较好的结构是菊花，于是在原树上选出若干不交菊花。按深度分成奇数层和偶数层，显然有一层是 \ge m 的。

考虑如何编号，要将它们排到链上使得 m 种距离均存在。手玩一下，把任意边数 >1 的菊花排在第一位来放 m,m-1，然后左右交替放即可，大概形如：

不难分析这样一定是合法的，证明大概就是一侧放到 x 之后下一个放的至多是 x-2。

同时这也要求存在边数 >1 的菊花。以任意 deg>1 的点为根，容易分析出按照上述方法选择则一定存在。

:::success[点击查看参考代码]

#include<bits/stdc++.h>
#define TIME chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count()
#define rep(i,l,r) for(int qwp=(r),i=(l);i<=qwp;i++)
#define per(i,r,l) for(int qwp=(l),i=(r);i>=qwp;i--)
#define pb push_back
#define SZ(x) (int)((x).size())
#define fir first
#define sec second
using namespace std;
namespace c0dE1ng{
typedef vector<int> arr;typedef pair<int,arr> ND;
constexpr int N=2005;
int n;arr g[N];int fa[N],de[N];vector<ND>f;bool mk[N];int p[N];
void dfs(int u){for(auto v:g[u])if(v!=fa[u])fa[v]=u,de[v]=de[u]+1,dfs(v);}
void main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n;rep(i,1,n-1){int x,y;cin>>x>>y;g[x].pb(y),g[y].pb(x);}
    int rt=1;while(SZ(g[rt])==1)rt++;dfs(rt);int sum=1;rep(i,1,n)if(!(de[i]&1))sum+=SZ(g[i])-1;
    int T=sum<n>>1;rep(i,1,n)if((de[i]&1)==T){arr t={};for(auto j:g[i])if(fa[j]==i)t.pb(j);f.pb({i,t});}
    rep(i,0,SZ(f)-1)if(SZ(f[i].sec)>1){swap(f[0],f[i]);break;}
    int l1=1,r2=n,t=n>>1;for(int i=0,j=0;i<SZ(f);i++){
        if(!SZ(f[i].sec)||!t)continue;
        if(j^=1){p[l1]=f[i].fir;for(auto u:f[i].sec)if(t)p[l1+t]=u,t--;l1++;}
        else{p[r2]=f[i].fir;for(auto u:f[i].sec)if(t)p[r2-t]=u,t--;r2--;}
    }
    rep(i,1,n)mk[i]=0;rep(i,1,n)mk[p[i]]=1;
    for(int i=1,j=1;i<=n;i++)if(!p[i]){while(mk[j])j++;p[i]=j,j++;}
    rep(_,1,n){rep(i,1,n)cout<<p[i]<<' ';cout<<'\n';rotate(p+1,p+2,p+1+n);}
}
}
int main(){
    auto _Tbe=TIME;c0dE1ng::main();auto _Ted=TIME;
    return cerr<<"\nTIME:"<<_Ted-_Tbe<<"ms\n",0;
}
/*
ulimit -s 1048576
g++ -O2 -std=c++14 -static A.cpp -o %;size %;./% < A.in > A.out
*/

:::