算法交流群_牛客博客

普通解法

除了群主牛牛，每个群友都有一个等级大于他的人作为朋友，那么最终是一个以牛牛为根的树。所以对于每个群友，一直往上找到第一个等级足够处理这个群友产生的问题上级，并统计答案。
当这个树是一个链的时候，最差时间复杂度为 $O(n^2)$
只用到少量中间变量存储计算值，空间复杂度 $O(1)$

vector&lt;int&gt; solve(int n, vector&lt;int&gt; a, vector&lt;int&gt; p, vector&lt;int&gt; k){
    vector&lt;int&gt; ans(n, 0);
    if(k[0] &lt;= a[0]) ans[0]++;
    for(int i = 1; i &lt; n; ++i) {
        int t = i;
        int val = k[i];
        while(t != 0 &amp;&amp; val &gt; a[t]) {
            t = p[t-1]-1;
        }
        if(val &lt;= a[t]) ans[t]++;

    }return ans;
}

最优解法

因为牛牛的编号是1且它全场最高。整棵树是以1为根的有根树。一个结点的权值一定大于它的子孙结点权值。整棵树呈堆的形式。
因为从根到一个结点的路径上，点的权值是越远离根结点，权值越小，满足二分性质。
树上倍增求得每个点向上 $2^i$ 层的祖先。求法为：用 $f[u][i]$ 表示结点 $u$ 向上跳 $2^i$ 层可以到达的结点。
然后在上面用类似二分的方法找到第一个能解决当前问题的祖先。
时间复杂度 $O(nlog(n))$
需要额外的空间存储倍增数组，空间复杂度 $O(nlog(n))$

int f[100005][20];
vector<int> g[100005];
void dfs(int u){
   // cout<<"u:"<<u<<endl;
    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]);
}
vector<int> solve(int n, vector<int> a, vector<int> p, vector<int> k){//1,n
    vector<int> ans(n, 0);
    for(int i = 0; i <= n; ++i) g[i].clear();
    memset(f, 0, sizeof f);
    for(int i = 0; i < n-1; ++i) f[i+2][0] = p[i],g[p[i]].push_back(i+2) ;
    dfs(1);
    if(k[0] <= a[0]) ans[0]++;
    for(int i = 1; i < n; ++i){
        if(k[i] <= a[i]){ans[i]++; continue;}
        int u = i+1;
        for(int j = 18; j >= 0; --j){
            if(f[u][j] == 0) continue;
            int t = f[u][j];
            if(k[i] > a[t-1]) u = t;
        }
        u = f[u][0];
        if(u == 0) continue;
        else ans[u-1]++;
    }return ans;
}