树上子链(dfs)

链接：https://ac.nowcoder.com/acm/contest/4462/B
来源：牛客网

给定一棵树 T ，树 T 上每个点都有一个权值。

定义一颗树的子链的大小为：这个子链上所有结点的权值和 。

请在树 T 中找出一条最大的子链并输出。

输入描述:

第一行输入一个 n,1≤n≤1e5。

接下来一行包含n个数，对于每个数 ai,−1e5≤ai≤1e5，表示 i 结点的权值。

接下来有n-1行，每一行包含两个数u，v（ 1≤u,v≤n, u != v），表示u与v之间有一条边。

输出描述:

仅包含一个数，表示我们所需要的答案。

示例1

输入

复制 5 2 -1 -1 -2 3 1 2 2 3 2 4 2 5

5
2 -1 -1 -2 3
1 2
2 3
2 4
2 5

输出

复制 4

4

说明

样例中最大子链为1 -> 2 -> 5

备注:

一个结点，也可以称作一条链

求树上最长子链：
不懂：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn=1e5+100;
struct node{
    int to,next; 
}edge[maxn];
int head[maxn];
int n;
ll a[maxn];
int cnt;
ll dp[maxn];
ll ans=-0x3f3f3f3f;
void add(int u,int v){
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
void dfs(int u,int fa){
    dp[u]=a[u];
    ans=max(ans,dp[u]);
    for(int i=head[u];~i;i=edge[i].next){
        int v=edge[i].to;
        if(v==fa){
            continue;
        }
        dfs(v,u);
        ans=max(ans,dp[v]+dp[u]);
        dp[u]=max(dp[u],dp[v]+a[u]);//不懂 
    }
}
int main(){
    memset(head,-1,sizeof(head));
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    } 
    int x,y;
    for(int i=1;i<=n-1;i++){
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }
    dfs(1,-1);
    cout<<ans<<endl;
    
}