https://www.luogu.com.cn/record/126957129

#include <bits/stdc++.h>
using namespace std;
int n, m, k, dis[2505][2505], g[2505][4];
long long w[2505], f[2505][4], ans;
vector<int> e[2505];
int main()
{
    cin >> n >> m >> k;
    for (int i = 2; i <= n; i++)
        cin >> w[i];
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
            dis[i][j] = 0x3f3f3f3f;
        queue<int> q;
        q.push(i);
        dis[i][i] = -1;
        while (q.size())
        {
            int u = q.front();
            q.pop();
            for (int &v : e[u])
            {
                if (dis[i][v] == 0x3f3f3f3f)
                {
                    dis[i][v] = dis[i][u] + 1;
                    q.push(v);
                }
            }
        }
    }
    memset(f, 0xc0, sizeof(f));
    for (int i = 2; i <= n; i++)
        for (int j = 2; j <= n; j++)
            if (i != j && dis[1][i] <= k && dis[i][j] <= k)
            {
                if (w[i] + w[j] > f[j][3])
                {
                    f[j][3] = w[i] + w[j];
                    g[j][3] = i;
                }
                if (f[j][3] > f[j][2])
                {
                    swap(f[j][3], f[j][2]);
                    swap(g[j][3], g[j][2]);
                }
                if (f[j][2] > f[j][1])
                {
                    swap(f[j][2], f[j][1]);
                    swap(g[j][2], g[j][1]);
                }
            }
    for (int i = 2; i <= n; i++)
        for (int j = 2; j <= n; j++)
            if (i != j && dis[i][j] <= k)
            {
                if (g[i][1] != j && g[j][1] != i && g[i][1] != g[j][1])
                    ans = max(ans, f[i][1] + f[j][1]);
                if (g[i][1] != j && g[j][2] != i && g[i][1] != g[j][2])
                    ans = max(ans, f[i][1] + f[j][2]);
                if (g[i][1] != j && g[j][3] != i && g[i][1] != g[j][3])
                    ans = max(ans, f[i][1] + f[j][3]);
                if (g[i][2] != j && g[j][1] != i && g[i][2] != g[j][1])
                    ans = max(ans, f[i][2] + f[j][1]);
                if (g[i][2] != j && g[j][2] != i && g[i][2] != g[j][2])
                    ans = max(ans, f[i][2] + f[j][2]);
                if (g[i][2] != j && g[j][3] != i && g[i][2] != g[j][3])
                    ans = max(ans, f[i][2] + f[j][3]);
                if (g[i][3] != j && g[j][1] != i && g[i][3] != g[j][1])
                    ans = max(ans, f[i][3] + f[j][1]);
                if (g[i][3] != j && g[j][2] != i && g[i][3] != g[j][2])
                    ans = max(ans, f[i][3] + f[j][2]);
                if (g[i][3] != j && g[j][3] != i && g[i][3] != g[j][3])
                    ans = max(ans, f[i][3] + f[j][3]);
            }
    cout << ans;
    return 0;
}