hihocoder #1851 : D级上司

向右看齐 2022-05-07 03:48 109阅读 0赞

时间限制: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;
    }