如何解决树节点祖先判断程序的超时问题？

核心问题定位 #

你的代码超时的主要原因是邻接表构建错误：在处理每个节点的直接祖先时，重复执行了g[anchestors[i]].push_back(i);两次，还额外添加了反向边g[i].push_back(anchestors[i]);。这会导致每个父节点到子节点的边被存储3次，DFS遍历的时候会反复处理这些重复边，时间复杂度从O(n)飙升到O(n²)，对于n=1e5的规模来说完全无法承受。

具体修复与优化方案 #

1. 修复邻接表构建逻辑 #

树是单向的父到子结构，构建邻接表时只需要添加父节点到子节点的单向边即可，不需要反向边，更不能重复添加：

for(int i=1; i<=n; ++i){
    readInt(anchestors[i]);
    if(anchestors[i] != 0) {
        // 仅添加父节点到子节点的单向边，消除冗余
        g[anchestors[i]].push_back(i);
    }else{
        start=i;
    }
}

2. 优化输入速度 #

把readInt里的getchar()替换为getchar_unlocked()，后者是无锁版本，输入速度更快（该函数在Linux环境下有效，绝大多数OJ均支持）：

void readInt(int &n){
    char ch;
    int sign = 1;
    while(ch = getchar_unlocked(), isspace(ch));
    n = 0;
    if(ch == '-')
        sign = -1;
    else n = ch - '0';
    while(ch = getchar_unlocked(), isdigit(ch))
        n = (n << 3) + (n << 1) + ch - '0';
    n *= sign;
}

3. 优化输出速度 #

单个cout输出1e5次会产生较大开销，建议把所有查询结果先存入字符串，最后一次性输出：

// 替换原查询循环
string res;
res.reserve(q * 2); // 预分配空间，避免多次扩容
while(q--){
    readInt(u),readInt(v);
    res += isAnchestor(u,v) ? "1\n" : "0\n";
}
cout << res;

同时打开cin.tie(0);，取消cin与cout的同步绑定，进一步提升输出效率：

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); // 取消注释该行
    cout.tie(0);
    // ... 其余代码
}

4. 修正DFS初始参数 #

根节点的parent应设为0（根节点无父节点，其祖先标记为0），避免出现逻辑错误：

dfs(start, 0);

5. 时间戳逻辑简化（可选） #

当前time_out使用++Time的方式可以简化，进入节点时time_in[node] = ++Time，离开时time_out[node] = Time，区间逻辑保持左闭右闭，判断逻辑不变但减少一次自增操作：

void dfs(int node,int parent){
    time_in[node] = ++Time;
    for(int &to : g[node]){
        if(to != parent){
            dfs(to, node);
        }
    }
    time_out[node] = Time; // 此处无需++Time
}

完整修复后的代码示例 #

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

vector<vector<int>> g;
vector<int> time_in, time_out;
int Time = 0;

void dfs(int node, int parent) {
    time_in[node] = ++Time;
    for (int &to : g[node]) {
        if (to != parent) {
            dfs(to, node);
        }
    }
    time_out[node] = Time;
}

bool isAnchestor(int anch, int node) {
    return time_in[anch] <= time_in[node] && time_out[anch] >= time_out[node];
}

void readInt(int &n) {
    char ch;
    int sign = 1;
    while (ch = getchar_unlocked(), isspace(ch));
    n = 0;
    if (ch == '-')
        sign = -1;
    else
        n = ch - '0';
    while (ch = getchar_unlocked(), isdigit(ch))
        n = (n << 3) + (n << 1) + ch - '0';
    n *= sign;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, start;
    readInt(n);
    time_in.resize(n + 1);
    time_out.resize(n + 1);
    g.resize(n + 1);
    vector<int> anchestors(n + 2);

    for (int i = 1; i <= n; ++i) {
        readInt(anchestors[i]);
        if (anchestors[i] != 0) {
            g[anchestors[i]].push_back(i);
        } else {
            start = i;
        }
    }

    dfs(start, 0);

    int q, u, v;
    readInt(q);
    string res;
    res.reserve(q * 2);
    while (q--) {
        readInt(u), readInt(v);
        res += isAnchestor(u, v) ? "1\n" : "0\n";
    }
    cout << res;

    return 0;
}

内容的提问来源于stack exchange，提问作者Isa