hihocoder #1851 : D级上司

时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述

H公司一共有N名员工，编号为1~N，其中CEO的编号是1。除了CEO之外，每名员工都恰好有唯一的直接上司；N名员工形成了一个树形结构。
我们定义X的1级上司是他的直接上司，2级上司是他上司的上司，以此类推……
请你找出每名员工的D级上司是谁。

输入
第一行包含2个整数N和D。
以下N-1行每行包含一个整数，依次代表编号是2-N的员工的直接上司的编号。
对于50%的数据，1 ≤ N, D ≤ 10000
对于100%的数据，1 ≤ N, D ≤ 100000

输出
依次输出1~N的D级上司的编号，每个一行。如果某员工没有D级上司，输出-1。

样例输入

5 2
1
1
3
3

样例输出

-1
-1
-1
1
1

递归解超时

#include <iostream>
#include <vector>

using namespace std;

int helper(int i,int j,vector<int>& m) {
    if(i==1&&j>0) {
        return -1;
    }
    if(j==0) {
        return i;
    }
     
    return helper(m[i],j-1,m);

}

int main() {
    
    int N,D;
    cin >> N >> D;
    
    vector<int> m(N+1,-1);
    
    for(int i=2;i<=N;++i) {
        int temp;
        cin >> temp;
        m[i] = temp;
    }
    D = min(N,D);
    
    for(int i=1;i<=N;++i)
        cout << helper(i,D,m) << endl;
    
    return 0;
}

将树转化为自顶向下dfs加上内存优化AC
时间空间复杂度均为o(n)

#include <iostream>
#include <vector>

using namespace std;

vector<int> v[100001];
vector<int> path(100001,-1);
vector<int> res(100001,-1);
int cur = 0;

void dfs(int i,int D) {
    path[cur] = i;
    ++cur;
    
    if(cur-D-1>=0)
        res[i] = path[cur-D-1];
    else res[i] = -1;
    
    for(auto each:v[i]) 
        dfs(each,D);
    --cur;
}

int main() {

    int N,D;
    cin >> N >> D;
    
    for(int i=0;i<N;++i) {
        int temp;
        cin>>temp;
        v[temp].push_back(i);
    }

    dfs(1,D);
    
    for(int i=1;i<=N;++i)
        cout << res[i] << endl;

    return 0;
}