科大讯飞笔试第三批 第三题补题

树上DP，就说求以根节点出发的最长节点值非减的深度+次长节点值非减的深度，能够构成一个链。非增同理

有向图+记忆化搜索dfs

做题的时候结果读取逻辑写乱了，最后没通过，还得练

#include <iostream>
#include <vector>
#include <cmath>
#include<string.h>
using namespace std;
const int M=1e5+5;
#define lld long long int

int n,v[M],dp[M];
vector<int> to[M];

int dfs(int x){
    if(dp[x]!=-1)return dp[x];
    int cur=0;
    for(int j: to[x]){
        if(v[x]<=v[j]){
            cur=max(cur,dfs(j));
            cout<<"dp"<<j<<"--"<<endl;
        }
    }
    return dp[x]=cur+1;
}


int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>v[i];
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        to[a].push_back(b);
    }
    memset(dp,-1,sizeof(dp));
    lld ans=0,m1=0,m2=0;
    dfs(1);
    for(int i=1;i<=n;i++)cout<<"dp"<<i<<"="<<dp[i]<<endl;
    for(int j: to[1]){
        lld now_m=dp[j];
        if(now_m>m1)m2=m1,m1=now_m;
        else if(now_m>m2)m2=now_m;
    }
    ans=m1+m2+1;
    cout<<ans<<endl;
    return 0;
}