题解：P13346 [EGOI 2025] Laser Strike / 激光突击

lnw143 · 2025-11-08 22:18:54 · 题解

题目大意

通信题，给 Alice 一棵树，Alice 需要给出这棵树的一个拓扑序（根任意），并给出传递给 Bob 的额外信息 01 串 s，要求 |s| \le 1。

Bob 需要根据额外信息串还原该拓扑序，交互库每次会给出一条树边 (u,v)，满足 u,v 目前都没被删并且 u,v 中存在一个点是这一步应删的叶子，Bob 需要判断 u,v 哪一个应当被删。

菊花

比较显然，传递第一条边删哪个的信息，剩余每条边与前一条重合的点为根，保留即可。

链

如果只针对该子任务可以想到删与上一条重合的点，但是与菊花做法冲突。

考虑保留菊花做法，那么把链的中点拿出来作根，先花费两个 bit 给出初始两个叶子编号，然后在链两端反复横跳删叶子。

Bob 之所以能识别第三步及之后的叶子，是因为它在之前出现过又不是上一次出现的点，据此判断即可。

然而 2bit 并不节俭，考虑如何消去 1bit。

我们发现这 1 bit 可以通过前两条边的大小关系传递，具体地，为边与边规定一个偏序关系（一个例子是比较 (u,v) 无序对的字典序），如果前两条边的 bit （指叶子较小为 0，叶子较大为 1）相同，则把小的放在前面，否则把大的放在前面，最后传递第一条边的 bit 即可。

Bob 只需判断第二条边与第一条边的大小就知道第二条边的 bit 了。

需要特殊处理点数为偶数情况。

正解

考虑沿用上面的策略。

容易发现 Bob 按以下规则操作：

• 第一条边：根据额外信息判断。
• 当前边与上一条边有共点：删掉不共的点。
• 当前边恰有一个点在之前出现过：删掉该点。

然而依然会存在都不满足的情况，即别处的叶子，对 Bob 来说它的信息是完全未知的，但我们先不管。

假设 Bob 有能力获知「新叶子」的信息，考虑 Alice 如何构造拓扑序使得 Bob 能正确地删空叶子。

首先拉出直径，以中点为根（直径长度奇数时以中间两点为根，即两点深度都为 0）建树，对于非叶结点，如果它的儿子全为叶子，那么它需要一次「新叶子」操作来清空儿子，即先删一个「新叶子」，然后按菊花情况清空儿子。

此时局面上所有原有叶子已经删除，并且将要被删除的叶子都已出现过，我们唯一需要考虑的是不能删完一个点儿子后迅速删除该点，否则会判为菊花情况而把它父亲删掉。

考虑深度从大往小清点，由于选的是直径中点为根，当前层一定有两个以上的点，只有一个是上层最后删去的叶子的父亲，指定它不是下一个被删的点即可。

需要注意的是如果一个叶子被删除，它的兄弟叶子应当被立马删除，因为这样成本最低且保证正确性（指一个非叶点存在非叶儿子，那么非叶儿子被删除时会把叶儿子全部清空，故该点不需要「新叶子」操作）。

最后特判两个根的情况，用菊花的策略即可。

于是我们剩下最后一个问题：Bob 如何获知「新叶子」的信息？

考虑沿用链的策略，即：每出现一个「新叶子」，Bob 会拿它与上一个「新叶子」比较大小，如果上一个「新叶子」更大，则沿用上一个 bit，否则取反。

发现 Alice 的构造也很简单：初始把所有「新叶子」排序，对每个极长相等 bit 段做 reverse 即可。

注意删一个「新叶子」时也要立马清除叶子兄弟，但是这些点并不是「新叶子」。

回顾

总结一下，Alice 的策略是：

先以直径中点（可能是两个）为根建树，按深度分层。

对于非叶节点，如果它儿子全为叶子，提出任意一个儿子作为「新叶子」。

• 将「新叶子」排序，并 reverse 所有「新叶子」 bit 极长相等段，按序删除。
• 任意时刻，若上次删除的叶子的父亲有叶儿子，立马删除。
• 如果当前删除的是该层第一个点，特殊判断该点是不是上次删除叶子的父亲，是的话换一个点删除。
• 否则任意删除当前层的一点，若删空移至下一层。

最后特殊处理两个根的情况。

Bob 的策略是：

• 第一条边：用额外信息判断，记为「新叶子」。
• 和上一条边有共点：删掉不共点。
• 其中一点出现过：删掉出现过的点。
• 判断该边与上一条「新叶子」边的大小以获得它的 bit，记该边为「新叶子」。

注意以上策略具有优先级。

:::info[代码]

const int N=1e3;
int tp,tot,diam,n,d[N+2],deg[N+2],fa[N+2];
vector<int> e[N+2],f[N+2],g[N+2];
pair<int,int> lst;
bool bz[N+2];
pair<int,int> E(int x,int y) {
    return x<y?make_pair(x,y):make_pair(y,x);
}
void dfs(int u,int p) {
    fa[u]=p;
    for(auto v : e[u]) if(v!=p) {
        ++deg[u];
        d[v]=d[u]+1;
        dfs(v,u);
    }
}
pair<int,int> getrt() {
    dfs(0,-1);
    int x=max_element(d,d+n)-d;
    d[x]=0;
    dfs(x,-1);
    int y=max_element(d,d+n)-d;
    diam=d[y];
    for(int i=0; i<diam/2; ++i) y=fa[y];
    if(diam&1) return {fa[y],y};
    return {y,-1};
}
void put(int u) {
    ++tot;
    cout<<u<<endl;
    lst={u,fa[u]};
    bz[u]=1;
    if(fa[u]!=-1) {
        if(!--deg[fa[u]]&&fa[fa[u]]!=-1) f[fa[fa[u]]].push_back(fa[u]);
        while(f[fa[u]].size()&&bz[f[fa[u]].back()]) f[fa[u]].pop_back();
        if(f[fa[u]].size()) put(f[fa[u]].back());
    }
}
void solve1() {
    for(int i=0; i<n-1; ++i) {
        int x,y;
        cin>>x>>y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    auto [rt,rt1]=getrt();
    memset(deg,0,sizeof(deg));
    d[rt]=0,dfs(rt,rt1);
    fa[rt]=-1;
    if(rt1!=-1) d[rt1]=0,dfs(rt1,rt),fa[rt1]=-1;
    cerr<<"root="<<rt<<","<<rt1<<'\n';
    int maxd=*max_element(d,d+n);
    vector<pair<int,int>> s;
    for(int i=0; i<n; ++i) {
        int c=0;
        for(auto j : e[i]) if(e[j].size()==1) ++c;
        if(e[i].size()>1&&c+1>=e[i].size()) bz[i]=1;
    }
    for(int i=0; i<n; ++i) if(!deg[i]&&fa[i]!=-1) f[fa[i]].push_back(i);
    for(int i=0; i<n; ++i) if(e[i].size()==1) {
        if(!bz[fa[i]]) continue;
        bz[fa[i]]=0;
        s.emplace_back(i,fa[i]);
    }
    sort(s.begin(),s.end(),[](auto x,auto y) { return E(x.fi,x.se)<E(y.fi,y.se); });
    for(int i=0; i<s.size(); ++i) {
        int j=i;
        while(j+1<s.size()&&(s[i].fi<s[i].se)==(s[j+1].fi<s[j+1].se)) ++j;
        reverse(s.begin()+i,s.begin()+j+1);
        i=j;
    }
    cout<<"01"[s[0].fi>s[0].se]<<'\n';
    for(auto [i,j] : s) put(i);
    for(int i=0; i<n; ++i) if(e[i].size()!=1) g[d[i]].push_back(i);
    for(int cur=maxd,lim=n-1-(diam&1); cur>0&&tot<lim; ) {
        while(g[cur].size()&&bz[g[cur].back()]) g[cur].pop_back();
        if(g[cur].empty()) {
            --cur;
            if(!cur) break;
            if(g[cur].back()==lst.se) swap(g[cur].front(),g[cur].back());
            put(g[cur].back());
            continue;
        }
        put(g[cur].back());
    }
    if(diam&1) put(lst.se^rt^rt1);
}
void solve2() {
    static int a[N+2],b[N+2];
    string s;
    cin>>s;
    int x=s[0]=='1';
    pair<int,int> pre;
    for(int i=0; i<n-1; ++i) {
        cin>>a[i]>>b[i];
        if(!i) {
            pre={a[i],b[i]};
            if(x) swap(a[i],b[i]);
        } else if(a[i]==b[i-1]||b[i]==b[i-1]) {
            if(a[i]==b[i-1]) swap(a[i],b[i]);
        } else if(bz[a[i]]||bz[b[i]]) {
            if(bz[b[i]]) swap(a[i],b[i]);
        } else {
            x^=(pre<make_pair(a[i],b[i]));
            pre={a[i],b[i]};
            if(x) swap(a[i],b[i]);
        }
        cout<<a[i]<<endl;
        d[b[i]]=max(d[b[i]],d[a[i]]+1);
        bz[b[i]]=1;
    }
}

:::