How do I resolve the time limit?

Question

Write a program that determines for two nodes of a tree whether the first one is a parent of another.

Input data The first line contains the number of vertices n (1 ≤ n ≤ 10^5) in a tree. The second line contains n numbers, the i-th one gives the vertex number of direct ancestor for the vertex i. If this value is zero, then the vertex is a root of a tree.

The third line contains the number of queries m (1 ≤ m ≤ 10^5). Each of the next m lines contains two different numbers a and b (1 ≤ a, b ≤ n).

Output data For each of the m queries print on a separate line number 1, if the vertex a is one of the parents of a vertex b, and 0 otherwise.

Input example #1

6

0 1 1 2 3 3

5

4 1

1 4

3 6

2 6

6 5

Output example #1

0

1

1

0

0

Problem

How can I fix the time limit? I also tried with <stdio.h>(scanf();printf()). But problem gives time limit. It gives time limit for input(many input things) My solution:

#include<iostream>
#include<vector>
#include<algorithm>
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;// or  time_out[node]=Time;
}
bool isAnchestor(int anch,int node){
    return time_in[anch]<=time_in[node] and time_out[anch]>=time_out[node];
}
void readInt(int &n){
    char ch;
    int sign = 1;
    while(ch = getchar(), isspace(ch)){//getchar()-->getchar_unlocked()

    };
    n = 0;
    if(ch == '-')
        sign = -1;
    else n = ch - '0';
    while(ch = getchar(), 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){// I am thinking: the anchestors is sorted.
            readInt(anchestors[i]);
            if(anchestors[i] != 0) {


        g[anchestors[i]].push_back(i);
        g[i].push_back(anchestors[i]);
        g[anchestors[i]].push_back(i);
    }else{
    start=i;
    }
    }
    dfs(start,1);
    int q,u,v;
    readInt(q);
    while(q--){
        readInt(u),readInt(v);
        cout<<isAnchestor(u,v)<<'\n';// The anchestor of v is u. //(u,v)-->(a,b)
    }
    return 0;
}

Answer 1

Your approach using a depth first search is inefficient. This in general will look at more than just the path from b to a though the "parent pointers" or to the root, if b is not a descendant of a.

Instead start the search at b and go to the parent node repeatedly until you find the root or a. This will only consider the path from b to the root node. You don't need to consider any alternative paths, but you always know the edge to traverse.

#include <iostream>
#include <vector>

int main()
{
    constexpr int RootParent = -1;

    int n;
    std::cin >> n;
    std::vector<int> parents;
    parents.reserve(n);
    for (int i = 0; i != n; ++i)
    {
        int v;
        std::cin >> v;
        parents.push_back(v - 1); // note: storing 0-based indices of parents here (root's parent becomes -1)
    }

    int queryCount;
    for(std::cin >> queryCount; queryCount > 0; --queryCount)
    {
        int searchedAncestor;
        int descendant;
        std::cin >> searchedAncestor >> descendant;
        
        // inputs are still 1-based, so we need to decrement here
        --searchedAncestor;
        --descendant;

        // repeatedly go to the parent node until we reach the root or the ancestor to attempt to find
        while ((searchedAncestor != descendant) && (descendant != RootParent))
        {
            descendant = parents[descendant];
        }
        std::cout << (searchedAncestor == descendant) << '\n';
    }
}

Demo on godbolt