好的，我来根据上述分析写出这道题的完整题解。

「POI2017 R3」米达斯 Midas 题解

题目大意

给定一个 $n$ 个节点的二叉树（每个节点最多有两个子节点，分别称为左、右子节点），根节点为 $1$。
从根节点出发，每次经过左通道费用 = 当前总费用，经过右通道费用 = 当前总费用 + 1。
有 $z$ 个查询，每个查询给出 $x, y$，问：从根到 $x$ 的费用是否足够支付从根到 $y$ 的费用（即费用相等或 $x$ 的费用更少）。

解题思路

1. 费用与二进制的关系

观察费用的计算方式：

• 初始费用为 0（在根节点）。
• 走左通道：费用不变。
• 走右通道：费用 +1。

这实际上等价于一个二进制数的构建过程：

• 走左通道相当于在二进制数末尾添加一个 0。
• 走右通道相当于在二进制数末尾添加一个 1。

因此，从根到任意节点 $u$ 的路径可以表示为一个二进制数，其值就是所需费用。

2. 查询的本质

设：

• $cost(x)$ = 从根到 $x$ 的费用（二进制数值）。
• $cost(y)$ = 从根到 $y$ 的费用。

查询问：$cost(x)$ 是否足够支付 $cost(y)$，即 $cost(x) \le cost(y)$ 吗？

但这里有一个关键点：由于路径是唯一的，$cost(x)$ 和 $cost(y)$ 的二进制表示其实就是路径的 0/1 序列。
实际上，$cost(x)$ 足够支付 $cost(y)$ 当且仅当 $x$ 的路径是 $y$ 的路径的前缀。

为什么？

• 如果 $x$ 的路径是 $y$ 的路径的前缀，那么从根到 $y$ 会先经过 $x$，所以 $cost(y)$ 的二进制表示的前若干位等于 $cost(x)$，后面可能还有位，因此 $cost(y) \ge cost(x)$。
• 如果 $x$ 的路径不是 $y$ 的路径的前缀，那么在某一位它们分叉，$x$ 走的是 0 分支，$y$ 走的是 1 分支，则 $cost(x) < cost(y)$ 仍然成立吗？
  实际上要小心：如果 $x$ 路径不是 $y$ 路径前缀，那么在某一位 $x$ 是 1 而 $y$ 是 0，则 $cost(x) > cost(y)$，此时答案就是 NIE。

更精确的结论：
$cost(x) \le cost(y)$ 当且仅当 $x$ 的二进制路径是 $y$ 的二进制路径的二进制前缀（即从高位到低位比较，$x$ 的路径序列是 $y$ 的路径序列的前缀）。

3. 实现方法

1. DFS 遍历：从根节点开始 DFS，记录每个节点的路径二进制表示（用一个整数 val[u] 表示，每次左移一位，选择左子节点不加位，选择右子节点加 1）。
2. 路径长度：同时记录每个节点的路径长度（二进制位数）len[u]。
3. 查询判断：对于查询 $(x, y)$，取 $val[x]$ 和 $val[y]$ 的前 $len[x]$ 位比较，如果相等则是前缀关系，输出 TAK，否则 NIE。

具体比较方法：

• 如果 $len[x] > len[y]$，则 $x$ 不可能是 $y$ 的前缀，输出 NIE。
• 否则，将 $val[y]$ 右移 $(len[y] - len[x])$ 位，与 $val[x]$ 比较，相等则 TAK，否则 NIE。

4. 复杂度分析

• 预处理 DFS：$O(n)$。
• 每个查询 $O(1)$。
• 总复杂度：$O(n + z)$，可以应对 $n, z \le 10^6$。

代码实现

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 1e6 + 5;

int l[MAXN], r[MAXN];
int val[MAXN], len[MAXN];

void dfs(int u, int v, int depth) {
    val[u] = v;
    len[u] = depth;
    if (l[u] > 0) dfs(l[u], v << 1, depth + 1);
    if (r[u] > 0) dfs(r[u], (v << 1) | 1, depth + 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    
    for (int i = 1; i <= n; i++) {
        cin >> l[i] >> r[i];
    }
    
    dfs(1, 0, 0);
    
    int z;
    cin >> z;
    
    while (z--) {
        int x, y;
        cin >> x >> y;
        
        if (len[x] > len[y]) {
            cout << "NIE\n";
        } else {
            int shift = len[y] - len[x];
            int prefix_y = val[y] >> shift;
            if (prefix_y == val[x]) {
                cout << "TAK\n";
            } else {
                cout << "NIE\n";
            }
        }
    }
    
    return 0;
}

总结

本题的关键在于将路径费用转化为二进制表示，并将查询转化为二进制前缀比较问题。
通过一次 DFS 预处理所有节点的路径值和长度，即可在 $O(1)$ 时间内回答每个查询。

这种将树路径编码为二进制数的方法，在解决类似“路径比较”问题时非常有用。