#sijdisd

🎈🎈🎈🎈🎈🎈🎈🎈

2026-08-08 14:30:29

发布于：浙江

6阅读

0回复

0点赞

@sevenstd

#include<bits/stdc++.h>
using namespace std;
int n;
vector<int>g[6003];
int a[6004];
int dp[6004][2];
void dfs(int u,int fa){
    dp[u][1]=a[u];
    for(auto v:g[u]){
        if(v==fa)continue;
        dfs(v,u);
        dp[u][0]=max(dp[u][0],max(dp[v][0],dp[v][1]));
        dp[u][1]=max(dp[u][1],dp[v][0]+a[u]);
    }
    //cout<<u<<" "<<dp[u][0]<<" "<<dp[u][1]<<endl;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int ans=-1e9;
    for(int i=1;i<=n;i++){
        memset(dp,0,sizeof dp);
        dfs(i,0);
        ans=max(ans,dp[i][0]+dp[i][1]);
    }
    cout<<ans;
    return 0;
}