这题非求直径, 而是求树上最大的连续的片段

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

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

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

Face

tutorial:常规dfs, dp[i]代表该子树中最大的一条链(由叶子到根), 注意到有可能叶子的权全是负数, 所以我们吧res初始化负无穷

#include <bits/stdc++.h>
#include <bits/extc++.h>

using namespace std;
#define _rep(n, a, b) for (ll n = (a); n <= (b); ++n)
#define _rev(n, a, b) for (ll n = (a); n >= (b); --n)
#define _for(n, a, b) for (ll n = (a); n < (b); ++n)
#define _rof(n, a, b) for (ll n = (a); n > (b); --n)
#define oo 0x3f3f3f3f3f3f
#define ll long long
#define db double
#define eps 1e-6
#define bin(x) cout << bitset<10>(x) << endl;
#define what_is(x) cerr << #x << " is " << x << endl
#define met(a, b) memset(a, b, sizeof(a))
#define mp(a, b) make_pair(a, b)
#define all(x) x.begin(), x.end()
#define pii pair<ll, ll>
#define pdd pair<db, db>
#define pi acos(-1.0)
const ll maxn = 3e5 + 10;
const ll mod = 1e9 + 7;
ll n, a[maxn], res = -oo, dp[maxn];
vector<ll> G[maxn];
void dfs(ll cur, ll fa)
{
    dp[cur] = a[cur];
    for (auto to : G[cur])
    {
        if (to == fa)
            continue;
        dfs(to,cur);
        res = max(res, dp[cur] + dp[to]);//两个子树连起来
        dp[cur] = max( dp[cur], dp[to] + a[cur]);//选一个最大的子树连根
    }
    res = max(res, dp[cur]);

}
signed main()
{
    cin >> n;
    _rep(i, 1, n) cin >> a[i];
    _rep(i, 1, n - 1)
    {
        ll u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1, 0);
    cout << res << endl;
}