算法思路

本题是一个交互式问题，需要通过询问节点度数的异或值来推断整棵树的度数分布。核心思路是利用度数分布的性质和异或运算的特性来减少询问次数。

核心算法

1. 关键观察

• 对于任意树，所有节点的度数之和等于 $2 \times (N-1)$
• 询问 ? i j 得到 $deg(i) \oplus deg(j)$
• 如果固定一个节点（如节点1）询问所有其他节点，可以得到 $deg(1) \oplus deg(k)$ 对于 $k=2..N$

2. 算法步骤

步骤1：批量询问

for (int i = 1; i < N; i++) {
    cout << "? 1 " << i + 1 << '\n';
    q++;
    // 每10000次刷新一次缓冲区并读取答案
}

固定节点1，询问其与其他所有节点的度数异或值。

步骤2：统计异或值频次

while (q) {
    q--;
    int x;
    cin >> x;
    cnt[x]++;
}

统计每个异或值出现的次数。

步骤3：寻找候选度数

int mx = 0, sec = 1;
if (cnt[0] < cnt[1]) swap(mx, sec);
for (int i = 2; i < N + 1; i++) {
    if (cnt[i] > cnt[mx]) {
        sec = mx;
        mx = i;
    } else if (cnt[i] > cnt[sec])
        sec = i;
}

找到出现频次最高的两个异或值，它们对应的就是最可能的 $deg(1)$ 候选值。

步骤4：验证并输出

for (auto x : {mx, sec}) {
    int sm = 0;
    bool flag = 0;
    for (int i = 0; i < N + 1; i++) {
        sm += cnt[i] * (i ^ x ^ 1);
        flag |= cnt[i] > 0 && !(i ^ x ^ 1);
    }
    if (sm != 2 * N - 2 || flag) continue;
    // 输出结果
}

验证候选值是否满足度数总和为 $2N-2$ 且所有度数都为正整数。

算法标签

• 交互式问题 (Interactive Problem)
• 度数序列重构 (Degree Sequence Reconstruction)
• 异或性质 (XOR Properties)
• 频次统计 (Frequency Counting)
• 树的性质 (Tree Properties)

复杂度分析

• 时间复杂度: $O(N)$
  • 进行 $N-1$ 次询问
  • 统计和验证过程都是 $O(N)$
• 空间复杂度: $O(N)$ 用于存储频次统计

关键技巧解析

1. 异或运算的利用

设 $x = deg(1)$，那么对于询问 ? 1 k 得到的结果 $r_k = x \oplus deg(k)$ 因此 $deg(k) = x \oplus r_k$

2. 度数总和验证

利用树的性质：$\sum_{i=1}^N deg(i) = 2(N-1)$ 如果假设的 $x$ 正确，那么计算出的度数总和必须等于 $2N-2$

3. 候选值筛选

由于 $deg(1)$ 是未知的，但通过频次统计可以找到最可能的候选值：

• 出现频次最高的异或值对应的 $x$ 最可能是真实的 $deg(1)$
• 需要验证两个最频候选值

4. 缓冲区管理

cout << flush;

在大量询问时定期刷新输出缓冲区，避免超时。

正确性证明

1. 完备性: 通过询问节点1与所有其他节点的异或，获得了足够的信息来推断所有节点的度数。

2. 验证机制: 利用度数总和必须为 $2N-2$ 来验证候选解的正确性。

3. 候选值有限: 由于是树结构，节点的度数有明确的范围限制，候选值数量有限。

样例验证

对于样例1（N=4）：

• 询问 ? 1 2, ? 1 3, ? 1 4
• 统计异或值频次
• 找到候选 $deg(1)$ 值
• 验证并输出度数序列 1 3 1 1

该解法巧妙地利用了树的性质和异或运算的特性，在仅使用 $N-1$ 次询问的情况下成功重构度数序列，达到了最优的询问复杂度。