树上子链 题解

思路分析：

1.题目要求求解点权之和，这里区别一下点权和边权
2.求最大的子链：就是树的直径 =　ｍａｘ（最长链+次长链）
3.因为有负权，所以不能使用BFS或DFS

参考代码：

#include<bits/stdc++.h>

using namespace std;
const int N = 1e5+10, M = N * 2;／／双向边
const int inf = 0x3f3f3f3f;
typedef long long ll;

int n;
int h[N],e[M],ne[M],idx;
ll w[N];
ll ans = -inf;／／因为可能全部都是负数，所以答案初始为负无穷

void add(int a,int b){
    e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}

ll dfs(int u,int father){
    ll d1 = 0, d2 = 0;／／最长链、次长链初始为０
    for(int i = h[u];i != -1; i = ne[i] ){
        int j = e[i];
        if(j == father) continue;／／防止回头
        ll d = dfs(j,u);

        if(d >= d1) d2 = d1, d1 = d;／／更新最长和次长链
        else if(d > d2) d2 = d;／／更新次长链
    }
    ans = max(ans, d1 + d2 +w[u]);／／更新最优答案
    return d1+w[u];／／返回最长链上点的点权＋这个点的点权
}

int main(){
    cin >> n;
    memset(h,-1,sizeof h);
    for(int i = 1; i <= n; i ++ ) {
        cin >> w[i];
    }
    for(int i = 1; i <= n-1; i ++ ){
        int a,b;
        cin >> a >> b;
        add(a,b),add(b,a);
    }
    dfs(1,-1);
    printf("%lld",ans);
    return 0;    
}