树形dp之树的直径

题目：树上子链

树的最长子链（直径）= 以根为终点的最长子链 + 以根为终点的次长子链
f[i]表示以 i（根）为终点的最长子链

//树的直径有两种求法 
//1.树形DP（可以有效处理负边权）
//2.两次dfs或bfs（无法处理负边权）
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll const INF=0x3f3f3f3f3f3f3f3f;
int const N=1e5+7;
int n,cnt;
int head[N];
struct node{
    int a,next,len;
}edge[N<<1];
void add(int x,int y,int len){
    edge[++cnt].a =y;
    edge[cnt].len =len;
    edge[cnt].next =head[x];
    head[x]=cnt;
}
ll p[N],vis[N],f[N],ans=-INF;
void dfs(int x){
    f[x]=p[x];
    vis[x]=1;
    ll z1=-INF,z2=-INF;
    for(int i=head[x];i!=-1;i=edge[i].next){
        int u=edge[i].a ;
        if(vis[u]) continue;
        vis[u]=1;
        dfs(u);
        if(f[u]>z2){
            if(f[u]>z1){
                z2=z1;
                z1=f[u];
            }
            else z2=f[u];
        }
    }
    ll z=max(f[x],max(z1+f[x],z1+z2+f[x]));
    ans=max(ans,z);
    f[x]=max(f[x],f[x]+z1);
    //f[x]=max(f[x],z);
    //cout << x << " " << f[x] << endl;
}
int main(){
    cin >> n;
    memset(head,-1,sizeof(head));
    memset(f,-0x7f,sizeof(f));
    for(int i=1;i<=n;++i){
        int a;
        cin >> a;
        p[i]=a;
    }
    for(int i=1;i<=n-1;++i){
        int a,b;
        cin >> a >> b;
        add(a,b,0);add(b,a,0);
    }
    dfs(1);
    cout << ans ;
    return 0;
}