思路与算法

从给定根做显式DFS，记录首次进入tin和整个子树完成时的tout。x为y祖先的条件是tin[x]≤tin[y]≤tout[x]；先判断此条件输出1，再判断反向输出2，其余0。

正确性说明

DFS在离开某子树前不会进入其他子树，故每个子树的进入时间形成连续区间。编号的祖先关系等价于子树包含，两个方向的区间判断精确。相同节点落在自身区间，按第一条件输出1。

复杂度

节点号上界U=40000，初始化O(U)，建树遍历O(n)，m次查询O(m)，总O(U+n+m)时间，O(U+n)空间。

易错点

根由b=-1指定，不能假定编号1；编号可不连续。长链用显式栈。tout可用离开时的当前进入计数，不需要再加时间；比较包含端点。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<vector<int>> g(40001);
    int root = 0;
    for (int i = 0, a, b; i < n; i++) {
        cin >> a >> b;
        if (b == -1)
            root = a;
        else {
            g[a].push_back(b);
            g[b].push_back(a);
        }
    }
    vector<int> tin(40001), tout(40001), par(40001), pos(40001), st(1, root);
    int tim = 0;
    tin[root] = ++tim;
    while (!st.empty()) {
        int u = st.back();
        if (pos[u] < (int)g[u].size()) {
            int v = g[u][pos[u]++];
            if (v == par[u])
                continue;
            par[v] = u;
            tin[v] = ++tim;
            st.push_back(v);
        } else {
            tout[u] = tim;
            st.pop_back();
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y;
        bool a = tin[x] <= tin[y] && tin[y] <= tout[x], b = tin[y] <= tin[x] && tin[x] <= tout[y];
        cout << (a ? 1 : b ? 2 : 0) << '\n';
    }
}