题意

• 一颗有n个结点的树，每个结点具有权值，求解最长（权值最大）的一条子链

思路

• 对于某一个结点来思考，他能构成的最长子链无非下列集中情况之一
  • 包含他的最长链+最长的包含他一个儿子的最长链
  • 所有结点均为负值，最长子链自身的权值
  • 他自己的一条最长链（另一条全负）
• 因此我们维护一个dp数组，dp[i]表示包含结点i的最长子链，u是i的儿子，最终的为了避免dp[i]和dp[u]包含同一条子链，我们选择先更新res后更新dp[i]，由因为存在全负的可能性，所以每次遍历一颗子树时，ans的初值应该取到dp[i]

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[202020],dp[202020];
int res=-0x3f3f3f3f;
vector<int> t[202020];
void dfs(int x,int fa){
    dp[x]=a[x];
    res=max(res,dp[x]);
    for(auto i:t[x]){
        if(i==fa) continue;
        dfs(i,x);
        res=max(res,dp[x]+dp[i]);
        dp[x]=max(dp[x],dp[i]+a[x]);
    }
}
signed main(){
    int n;
    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 ;
        t[x].push_back(y);
        t[y].push_back(x);
    }
    dfs(1,0);
    cout << res << endl;
    return 0;
}