大家好，我是энтджей，今天是我2026年第六次正式发题解！（和上次跟新差了两个月（doge））

2026年发布的题解！

能不能点个赞

---

回归正题：

首先:

• 简单来说，题目就是让我们求最大的节点的所有比他小的子节点的个数

思路：

• 可以直接用dfs来写，搜所每一个节点比他小的子节点个数：

#include<bits/stdc++.h>
using namespace std;
int n;
int a[100010];
vector<int> ve[100010];
int ans = 0,sum;
bool vis[100010];
void dfs(int id){
    vis[id] = true;
    sum++;
    for(int i = 0;i < ve[id].size();i++){
        int t = ve[id][i];
        if(!vis[t] && a[id] > a[t]) dfs(t);
    }
}
int main(){
    cin >> n;
    for(int i = 1;i <= n;i++) cin >> a[i];
    for(int i = 1;i <  n;i++){
        int x,y;
        cin >> x >> y;
        ve[x].push_back(y);
        ve[y].push_back(x);
    }
    for(int i = 1;i <= n;i++){
        memset(vis,false,sizeof vis);
        sum = 0;
        dfs(i);
        ans = max(ans,sum);
    }
    cout << ans;
    return 0;
}

• 但这样会超时，因为每个节点不一定只会被搜索一次，所以要用记忆化搜索

#include<bits/stdc++.h>
using namespace std;
int n;
int a[100010];
vector<int> ve[100010];
int ans = 0;
int vis[100010];
int dfs(int id){
    if(vis[id] != -1) return vis[id];
    int sum = 0;
    for(int i = 0;i < ve[id].size();i++){
        int t = ve[id][i];
        if(a[id] > a[t]){
            sum += dfs(t);
        }
    }
    return vis[id] = sum + 1;
}
int main(){
    cin >> n;
    for(int i = 1;i <= n;i++) cin >> a[i];
    for(int i = 1;i <  n;i++){
        int x,y;
        cin >> x >> y;
        ve[x].push_back(y);
        ve[y].push_back(x);
    }
    memset(vis,-1,sizeof vis);
    for(int i = 1;i <= n;i++){
        ans = max(ans,dfs(i));
    }
    cout << ans;
    return 0;
}

---

🎉完结撒花🎉