题解：P16536 [THUPC 2026 决赛] 流光解密

· · 题解

这题怎么还能交题解？

蒟蒻的第一篇绿题以上题解、第一篇交互题题解，不喜勿喷。

题意

:::align{right} 详见原题 ::: 构造一种算法，将一个不大于 2^{n-1} 的正整数映射为一棵边有向的树，且能够根据树的形态还原出原数。

分析

不难想到边的方向实际上可以视为边权：由编号小的节点指向编号大的节点视为 1，否则视为 0。再结合 s 与 2 的幂相关的范围，显然需要二进制拆位。

一开始我尝试将 s-1 的二进制位与 n-1 条边的边权对应，但问题在于阶段一的边定向操作是在线的，我们事先不知道哪些节点间有直接连边，思路不可行。

我们尝试转换思路：我们不知道边的连接方式，但我们知道点的数量，那么我们可以将 s-1 拆位后作为点权，让边权反映两端节点的点权关系，这样正好剩下 1 个节点，可以将其作为点权固定的“参照物”。

这里我选择的映射方法是：两个相连的点，若两点点权相等，则两点间边权为 0，否则边权为 1；节点 1 的点权为 0，其余点的权由 s-1 拆位得到。

阶段一的策略确定后，我们还要考虑阶段二。将边的指向对应为边权，然后以节点 1 为根，对得到的树进行 DFS，不难发现子节点的点权就等于父节点点权与连边边权的异或。

代码

代码实现上，我偷了点懒，用 bitset 的构造函数实现拆位，用 bitset.to_ullong() 将点权序列转换为整数。

:::info[\textcolor{#52C41A}{\texttt{AC}} 代码]

#include <bits/stdc++.h>
using namespace std;
int T, Q;
void solve1();
void solve2();
vector< pair<int, bool> > G[35];
bitset<64> bs;
int main(){
    cin >> T >> Q;
    while(T--){
        if(Q == 1) solve1();
        else solve2();
    }
    return 0;
}
void solve1(){
    int n, s; cin >> n >> s;
    bitset<64> bs((s - 1) << 2);
    // 左移使得 s-1 的二进制位恰好被存储在 bs[2]~bs[n]
    for(int i = 1; i < n; i++){
        int a, b; cin >> a >> b;
        if(a > b) swap(a, b);
        if(bs[a] != bs[b]) swap(a, b); // 点权关系 -> 边权 -> 边的指向
        cout << a << ' ' << b << endl;
        // 交互题必须及时清空缓冲区，所以不能用 '\n' 代替 endl
    }
}
void dfs(int now, int fa){
    for(auto v: G[now]){
        if(v.first == fa) continue;
        bs[v.first] = bs[now] ^ v.second; // 边权 & 父节点点权 -> 子节点点权
        dfs(v.first, now);
    }
}
void solve2(){
    int n; cin >> n;
    for(int i = 1; i <= n; i++) G[i].resize(0);
    bs.reset();
    // 为了方便 dfs() 访问，邻接表和 bs 都是全局变量，所以多测要清空
    for(int i = 1; i < n; i++){
        int a, b; cin >> a >> b;
        G[a].push_back({b, a > b});
        G[b].push_back({a, a > b});
        // 边的朝向 -> 边权
    }
    dfs(1, 0); // 还原点权序列
    cout << (bs.to_ullong() >> 2) + 1; // bs.to_ullong() 等于 (s - 1) << 2
    cout << endl;
}

::: 你真的要看这坨石山吗？