RT

自己造了组样例，但是T掉了。。。

样例输入

7
502 1 100 50 3 4 5
1 2
1 3
1 4
2 5
2 6
5 7

样例输出

652

代码

#include <bits/stdc++.h>

#define rint register int
#define endl '\n'

using namespace std;

const int N = 2e5 + 5;
const int M = 4e5 + 5;
const int inf = 0x3f3f3f3f;

int idx, h[N], e[M], ne[M];
int d[N], w[N];
int ans = -inf;

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

void dfs(int x, int fa)
{
    d[x] = w[x];
    for (rint i = h[x]; i; i = ne[i])
    {
        int y = e[i];
        if (y == fa)
        {
            continue;
        }
        dfs(y, x);
        ans = max(ans, d[x] + d[y]);
        d[x] = max(d[x], d[y] + w[x]);
    }
    ans = max(ans, d[x]);
}

int main()
{
    int n;
    cin >> n;

    for (rint i = 1; i <= n; i++)
    {
        cin >> w[i];
    }

    for (rint i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }

    dfs(1, -1);

    cout << ans << endl;

    return 0;
}