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

GCSG01 · 2026-07-21 16:31:47 · 题解

显然要用二进制传递。
我们唯一能利用的是边的顺序，但边是在线给出的，考虑用点的编号。对于第 i 个点，令其表示二进制下该位为 1，则一条边的边权一定是通过点权间做运算得到的，注意到异或的优良性质使得我们可以通过一个叶子或根的权值逐步异或出所有的权值。
所以对于一条边 (u,v)，通过 val_u\oplus val_v 是否为 1,决定输出的顺序是从小到大还是从大到小。注意到我们要占用一位作为初始的信息，所以 s 要先减去一。

#include<bits/stdc++.h>
using namespace std;
const int N=55;
struct node{
    int v;
    bool w;
};
vector<node>e[N];
int f[N];
void solve1(){
    int n,s;cin>>n>>s,s--;
    memset(f,0,sizeof f);
    for(int i=1;i<n;i++)
        if((1<<(i-1))&s)f[i]=1;
    for(int i=1;i<n;i++){
        int u,v;cin>>u>>v;
        int flag=f[u]^f[v];
        if(flag)cout<<min(u,v)<<" "<<max(u,v)<<endl;
        else cout<<max(u,v)<<" "<<min(u,v)<<endl;
    }
    return ;
}
void dfs(int x,int v,int ffa){
    f[x]=v;
    for(auto y:e[x])
        if(y.v!=ffa)
            dfs(y.v,v^y.w,x);
    return ;
}
void solve2(){
    int n;cin>>n;
    memset(f,0,sizeof f);
    for(int i=1;i<=n;i++)
        e[i].clear();
    for(int i=1;i<n;i++){
        int u,v;cin>>u>>v;
        e[u].push_back({v,u<v});
        e[v].push_back({u,u<v});
    }
    dfs(n,0,0);
    int ans=0;
    for(int i=1;i<n;i++)
        if(f[i])ans+=(1<<(i-1));
    cout<<ans+1<<endl;
    return ;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int T,Q;cin>>T>>Q;
    if(Q==1)while(T--)solve1();
    else while(T--)solve2();
    return 0;
}