牛客小白月赛22 - B 树上子链（树的直径）

传送门：牛客小白月赛22 - B

题目描述

给定一棵树T，树上每个点都有一个权值。
定义一棵树的子链大小为：子链上的点的权值和。
请找出最大子链。

输入描述

第一行输入一个$n$,$1<=n<=10^5$
接下来一行包含$n$个数代表节点的权值，$-10^5<=a_i<=10^5$
接下来n-1行，每行u，v代表u，v之间有一条边

输出描述

输出答案

思路分析

树的直径，这里用dp法：
设dp[i]表示从节点i出发，往以i为根的子树走，能够走到的最大距离
因为题目是无根树，所以子链最大应该是以一个节点为根的最大值和次大值之和。
此题有单个节点的情况所以最后再取一次max。

样例输入

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

样例输出

4

AC代码

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <functional>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <iomanip>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

const int INF = 0x3f3f3f3f;
const int N=1e5+10;

vector<int>e[N];
ll ans=-1e16;
ll dp[N],a[N];

void dfs(int u,int fa) {
    dp[u]=a[u];
    for(auto v:e[u]) {
        if(v==fa)continue;
        dfs(v,u);
        ans=max(ans,dp[u]+dp[v]);
        dp[u]=max(dp[u],dp[v]+a[u]);
    }
    ans=max(ans,dp[u]);
}

int main() {
    IOS;
#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    int n;
    cin>>n;
    for(int i=1; i<=n; i++)cin>>a[i];
    for(int i=0; i<n-1; i++) {
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1,-1);
    cout<<ans<<endl;




    return 0;
}