方法思路

1. 这道题要求确定每个员工的授权请求对象，规则是：
   • 只能向上级提出申请
   • 申请对象是技术能力最接近的上级
   • 如果有多个技术能力相同的上级，选择组织架构上最近的
2. 解决步骤：
   • 构建企业的组织结构树（邻接表表示）
   • 对每个员工，从其直属领导开始向上遍历树，寻找技术能力最接近的上级
   • 使用深度优先搜索(DFS)或广度优先搜索(BFS)来找到从员工到最高领导的路径
   • 在这条路径上找到技术能力差异最小的上级
3. 优化：
   • 可以预先计算每个员工到树根的路径，避免重复搜索
   • 使用路径压缩技术减少查找路径的时间复杂度

代码实现

Java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        // 读取直属领导关系
        String[] leaders = br.readLine().split(" ");
        int[] directLeader = new int[n + 1];
        for (int i = 1; i < n; i++) {
            directLeader[i] = Integer.parseInt(leaders[i - 1]);
        }
        
        // 读取技术等级
        String[] techs = br.readLine().split(" ");
        int[] techLevel = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            techLevel[i] = Integer.parseInt(techs[i - 1]);
        }
        
        // 为每个员工寻找授权请求对象
        StringBuilder result = new StringBuilder();
        for (int i = 1; i < n; i++) {
            // 使用BFS找到从员工i到最高领导的路径
            List<Integer> path = findPathToTop(i, directLeader);
            
            // 在路径上找到技术能力最接近的领导
            int closestLeader = findClosestLeader(i, path, techLevel);
            
            result.append(closestLeader);
            if (i < n - 1) {
                result.append(" ");
            }
        }
        
        System.out.println(result.toString());
    }
    
    // 找到从员工到最高领导的路径
    private static List<Integer> findPathToTop(int employee, int[] directLeader) {
        List<Integer> path = new ArrayList<>();
        int current = employee;
        
        while (directLeader[current] != 0) {
            path.add(directLeader[current]);
            current = directLeader[current];
        }
        
        return path;
    }
    
    // 在路径上找到技术能力最接近的领导
    private static int findClosestLeader(int employee, List<Integer> path, int[] techLevel) {
        int minDiff = Integer.MAX_VALUE;
        int closestLeader = -1;
        
        for (int leader : path) {
            int diff = Math.abs(techLevel[employee] - techLevel[leader]);
            
            // 如果找到更接近的领导，或者相同技术差异但组织上更近的领导
            if (diff < minDiff) {
                minDiff = diff;
                closestLeader = leader;
            }
        }
        
        return closestLeader;
    }
}

Python

def main():
    n = int(input())
    
    # 读取直属领导关系
    leaders = list(map(int, input().split()))
    direct_leader = [0] * (n + 1)
    for i in range(1, n):
        direct_leader[i] = leaders[i - 1]
    
    # 读取技术等级
    tech_levels = list(map(int, input().split()))
    tech_level = [0] + tech_levels  # 索引从1开始
    
    # 为每个员工寻找授权请求对象
    result = []
    for i in range(1, n):
        # 找到从员工i到最高领导的路径
        path = find_path_to_top(i, direct_leader)
        
        # 在路径上找到技术能力最接近的领导
        closest_leader = find_closest_leader(i, path, tech_level)
        
        result.append(str(closest_leader))
    
    print(' '.join(result))

# 找到从员工到最高领导的路径
def find_path_to_top(employee, direct_leader):
    path = []
    current = employee
    
    while direct_leader[current] != 0:
        path.append(direct_leader[current])
        current = direct_leader[current]
    
    return path

# 在路径上找到技术能力最接近的领导
def find_closest_leader(employee, path, tech_level):
    min_diff = float('inf')
    closest_leader = -1
    
    for leader in path:
        diff = abs(tech_level[employee] - tech_level[leader])
        
        # 如果找到更接近的领导，或者相同技术差异但组织上更近的领导
        if diff < min_diff:
            min_diff = diff
            closest_leader = leader
    
    return closest_leader

if __name__ == "__main__":
    main()

C++

#include <iostream>
#include <vector>
#include <climits>
#include <cmath>
using namespace std;

// 找到从员工到最高领导的路径
vector<int> findPathToTop(int employee, vector<int>& directLeader) {
    vector<int> path;
    int current = employee;
    
    while (directLeader[current] != 0) {
        path.push_back(directLeader[current]);
        current = directLeader[current];
    }
    
    return path;
}

// 在路径上找到技术能力最接近的领导
int findClosestLeader(int employee, vector<int>& path, vector<int>& techLevel) {
    int minDiff = INT_MAX;
    int closestLeader = -1;
    
    for (int leader : path) {
        int diff = abs(techLevel[employee] - techLevel[leader]);
        
        // 如果找到更接近的领导，或者相同技术差异但组织上更近的领导
        if (diff < minDiff) {
            minDiff = diff;
            closestLeader = leader;
        }
    }
    
    return closestLeader;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    
    // 读取直属领导关系
    vector<int> directLeader(n + 1, 0);
    for (int i = 1; i < n; i++) {
        cin >> directLeader[i];
    }
    
    // 读取技术等级
    vector<int> techLevel(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> techLevel[i];
    }
    
    // 为每个员工寻找授权请求对象
    for (int i = 1; i < n; i++) {
        // 找到从员工i到最高领导的路径
        vector<int> path = findPathToTop(i, directLeader);
        
        // 在路径上找到技术能力最接近的领导
        int closestLeader = findClosestLeader(i, path, techLevel);
        
        cout << closestLeader;
        if (i < n - 1) {
            cout << " ";
        }
    }
    cout << endl;
    
    return 0;
}