rt.

大致思路是把完整的路径1->a->b->c->d->1拆分成->->b和1->d->c，用$O(n^2)$的时间复杂度处理好拆分后答案，然后再遍历所有点选出使答案最大的b点和c点，把答案整合起来

不知道有没有没注意到的细节和没考虑到的情况

请多多指教orz

#include <cstring>
#include <iostream>
#include <queue>

using namespace std;

const int N = 2510;

int n, m, k;
long long w[N];   //点权
int dis[N][N];    //点之间的距离
bool st[N];       //bfs时记录是否已经走过
long long cal[N]; //计算1->a->b（1->d->c）
long long ans;    //最终答案

char buf[1 << 20], *head = buf, *tail = buf;

inline char input() //超级快读
{
    if (head == tail)
        tail = (head = buf) + fread(buf, 1, 1 << 20, stdin);
    return *head++;
}

template <typename T1>
inline void read(T1& x) //快读
{
    x = 0;
    char ch = input();
    while (!isdigit(ch))
        ch = input();
    while (isdigit(ch)) {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = input();
    }
}

inline void write(const long long x) //快写
{
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + 48);
}

inline void bfs(const int sp) //bfs求边权都为1的最短路，且所有点肯定都被更新到了
{
    memset(st, 0, sizeof(st));
    queue<int> q;
    q.push(sp);
    st[sp] = 1;
    while (!q.empty()) {
        int tmp = q.front();
        q.pop();
        for (int i = 1; i <= n; i++) {
            if (!st[i] && dis[tmp][i] == 1) {
                st[i] = 1;
                dis[sp][i] = dis[i][sp] = dis[sp][tmp] + 1;
                q.push(i);
            }
        }
    }
}

inline bool check(const int u, const int v) //最后寻找路径时检查路径合法性
{
    if (u == v) //两点相同
        return 0;
    if (dis[u][v] > k + 1) //两点之间距离过远
        return 0;
    return 1; //合法的
}

int main()
{
    read(n), read(m), read(k);
    for (int i = 2; i <= n; i++)
        read(w[i]);
    while (m--) {
        int u, v;
        read(u), read(v);
        dis[u][v] = dis[v][u] = 1;
    }
    for (int i = 1; i <= n; i++) //每个点跑一边bfs求到另外所有点的最短路，相当于floyd，但是速度快（O(n^3)->O(n^2+nm)）
        bfs(i);
    for (int b = 2; b <= n; b++) //算一半答案
        for (int a = 2; a <= n; a++)
            if (check(1, a) && check(a, b))
                cal[b] = max(cal[b], w[a] + w[b]);
    for (int b = 2; b <= n; b++) //整合答案
        for (int c = 2; c <= n; c++)
            if (check(b, c))
                ans = max(ans, cal[b] + cal[c]);
    write(ans);
    return 0;
}