自动搬运

查看原文

来自洛谷，原作者为

	xxr___ CSP-S2025 rp++!

搬运于2025-08-24 23:12:52，当前版本为作者最后更新于2025-04-11 11:54:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

简单题，但是有坑。

首先根据异或的性质，一个定值 $x$ 如果存在一个数 $y$ 使得 $x\oplus z = y$ 那么这个 $z$ 是唯一的。

那么我们可以考虑枚举 $1$ 的度数，然后询问 $deg_1\oplus deg_i,i\ne 1$ 的值就能推出其他点的度数，因为一个树的度数只和是 $2\times n - 2$ 的所以只需要判断一下就行，这样就是 $O(n^2)$ 的做法。

发现异或实际上就是二进制的某一个两者只有其中一种是 1 的时候才会有贡献，所以可以考虑把 $deg_1\oplus deg_i$ 的值的二进制下每一位是 0 是 1 的数量记录下来，然后询问直接枚举位数就行，这样就是 $O(n\log n)$ 的了。

细节，由于度数不能是 $0$ 所以你枚举的度数不能存在一个 $i$ 满足 $deg_1\oplus deg_i = deg_1$。

代码：

#include<iostream>

const int N = 100005;
int n,q,xo[N],t[22],p[22];
bool vs[N << 3];
int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cin >> n >> q;
	for(int i = 2;i <= n; ++i){
		std::cout << "? "<< 1 <<' '<< i << '\n';
		std::cout.flush();
		std::cin >> xo[i];
		for(int j = 0;j < 21; ++j){
			if(xo[i] >> j & 1){
				++ t[j];
			}else{
				++ p[j];
			}
		}
		vs[xo[i]] = 1;
	}
	for(int i = 1;i < n; ++i){
		int ans = i;
		for(int j = 0;j < 21; ++j){
			if(!(i >> j & 1)){
				ans += t[j] * (1 << j);
			}else{
				ans += p[j] * (1 << j);
			}
		}
		if(ans == 2 * n - 2 && !vs[i]){
			std::cout << "! ";
			std::cout.flush();
			std::cout << i << ' ';
			for(int j = 2;j <= n; ++j){
				std::cout << (i ^ xo[j]) << ' ';
			}
			std::cout.flush();
			return 0;
		}
	}
	return 0;
}