题解 | #算法交流群#

思路：

题目的主要信息：

三个数组，a表示每个人能够解决的问题的最大等级（首位必然最大），p为除a的首位外每个人拥有的能比自己能够解决更大等级问题的朋友，自己不能解决的问题可以交给朋友，k表示每个人产生的问题等级。
当某个人产生一个问题，自己能够解决就自己解决，自己不行就交给朋友，朋友不行再给朋友的朋友，依次类推，直到a的首位不能解决，则放弃
求a中每个人解决的问题数

关键点：谁产生的问题，谁优先解决，不行再往更高处交移

方法一：暴力法
具体做法：
遍历问题，对于每个问题，优先给自己解决，不行交给朋友，朋友不行再交给朋友的朋友，直到推到首位，再检查首位能不能解决。
图片说明

class Solution {
public:
    vector<int> solve(int n, vector<int>& a, vector<int>& p, vector<int>& k) {
        vector<int> res(n, 0);
        for(int i = 0; i < n; i++){
            if(k[i] <= a[i]){ //自己可以解决
                res[i]++;
                continue;
            }
            else if(i == 0) //牛牛不能解决
                continue;
            int temp = p[i - 1]; //朋友的序号，不是下标，所以下面都要多减1
            while(temp != 1){ 
                if(a[temp - 1] >= k[i]){  //朋友解决
                   res[temp - 1]++;
                   break;
                }
                temp = p[temp - 2];
            }
            if(temp == 1 && a[0] >= k[i]) //牛牛解决
                res[0]++;
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O(n^2)$ ，最坏情况每个都要牛牛解决或者牛牛都不能解决，则需要遍历两层
空间复杂度： $O(1)$ ，常数空间，其中res是返回函数必要空间，不算额外空间

方法二：树+递归
具体做法：
因为首位牛牛的编号是最高的，它是没有求助的朋友的，而比它次一点的一个或者多个节点的朋友是它，再依次往下推。那么，我们可以把这种朋友关系看成是树的父子关系，孩子节点解决不了的问题，我们往上找父节点，最终到根节点，也就是牛牛，我们以某个解决能够解决的最大问题作为树的权值，那么该树一定是大顶堆型的树。
因为从根到一个结点的路径上，点的权值是越远离根结点，权值越小，因此满足二分性质。树上倍增求得每个点向上 $2^i$ 层的祖先，我们可以用 $f[t][i]$ 表示结点 $t$ 向上跳 $2^i$ 层可以到达的结点，在建树的时候就把这个数组完善。

class Solution {
public:
    void dfs(int u, vector<vector<int>>& g, vector<vector<int>>& f){ //建立树
        for(int i = 0; i < 19; i++) 
            f[u][i + 1] = f[f[u][i]][i];
        for(int i = 0; i < g[u].size(); i++)
            dfs(g[u][i], g, f); //递归
    }
    vector<int> solve(int n, vector<int>& a, vector<int>& p, vector<int>& k) {
        vector<int> res(n, 0);
        vector<vector<int> > f(n + 1, vector<int>(20)); //最多2^19层
        vector<vector<int> > g(n + 1); //记录对于每一层的子节点
        for(int i = 0; i < n - 1; i++){
            f[i + 2][0] = p[i];
            g[p[i]].push_back(i + 2);
        }
        dfs(1, g, f); //深度优先建树
        if(k[0] <= a[0])  //首位先验算
            res[0]++;
        for(int i = 1; i < n; i++){ 
            if(k[i] <= a[i]){ //自己解决
                res[i]++; 
                continue;
            }
            int temp = i + 1;
            for(int j = 18; j >= 0; j--){ //向上找
                if(f[temp][j] == 0) 
                    continue;
                int t = f[temp][j]; 
                if(k[i] > a[t - 1]) 
                    temp = t;
            }
            temp = f[temp][0];
            if(temp == 0) //牛牛不能解决
                continue;
            else res[temp - 1]++; //最近的解决位
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O(nlog_2n)$ ，每次从一个节点到根节点最多为 $O(log_2n)$ ，一共 $n$ 次
空间复杂度： $O(nlog_2n)$ ，建树时递归栈的最大空间