题解 | #树上子链#

思路

对于一个起始点x，最大子链是从x开始或者从x的子节点开始的最大子链。
答案是从x作为起始点得到的最大子链的最大值，起点在dfs过程中走一遍就不会超时了。
然后就是树形dp的问题啦。
坑点:要开ll，同时注意所有点权值都为负数的情况。

代码

#include<bits/stdc++.h>
#define int ll
#define inf 0x3f3f3f3f3f3f
typedef long long ll;
using namespace std;
const int maxn=1e5+5;
int n,a[maxn],u,v,tmp,ans,d[maxn];
vector<int>G[maxn];

void dfs(int node,int pre){
    d[node]=a[node];
    for(int i=0;i<G[node].size();i++){
        int to=G[node][i];
        if(to==pre) continue;
        dfs(to,node);
        ans=max(ans,d[to]+d[node]);
        d[node]=max(d[node],d[to]+a[node]);
    }
    ans=max(ans,d[node]);
}

signed main(){
    memset(d,-inf,sizeof(d));
    ans=-inf;
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    for(int i=1;i<n;i++){
        scanf("%lld%lld",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,0);
    cout<<ans;
    return 0;
}