考虑如果钦定了访问点的先后顺序就是一个无脑$O(n^2)$

dp,而答案四个点访问的先后顺序只有24种 也就是说我们随机钦定一个访问顺序有$1/24$的概率正确 直接$shuffle$到时限输出即可

已通过本题

（时限调到1981810更稳 1900000倒数第三个点可能挂）

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include <chrono>
#include <random>
#include<ctime>
#define Sakura int
#define Re register ll
#define _ putchar(' ') 
#define el putchar('\n')
#define ll long long
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout);

using namespace std;

const ll maxn=2500+10;
const ll inf=5e18;

inline ll read(){
	ll x=0,f=0;char c=getchar();
	while(!isdigit(c)) f|=c=='-',c=getchar();
	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return f?-x:x;
}

inline void ot(ll x){
	if(x<0) x=-x,putchar('-');
	if(x>9) ot(x/10);putchar(x%10|48);
}

vector<ll> G[maxn];
queue<ll> q;
ll n,m,K;
ll dis[maxn][maxn];
ll a[maxn];
ll b[maxn];
ll f[maxn][5];
ll ans;
bool vis[maxn];

inline void add(ll x,ll y){
    G[x].push_back(y);
}

inline void bfs(ll st){
    for(Re i=1;i<=n;++i) dis[st][i]=inf;
    dis[st][st]=0;
    for(Re i=1;i<=n;++i) vis[i]=false;
    vis[st]=true;
    q.push(st);
    while(!q.empty()){
        ll u=q.front();
        q.pop();
        for(auto v:G[u])
            if(!vis[v]){
                dis[st][v]=dis[st][u]+1;
                q.push(v);
                vis[v]=true;
            }
    }
}

double st,ed;

mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());

Sakura main(){
    st=clock();
    n=read(),m=read(),K=read()+1;
    for(Re i=2;i<=n;++i) a[i]=read();
    while(m--){
        ll x=read(),y=read();
        add(x,y);
        add(y,x);
    }
    for(Re i=1;i<=n;++i) bfs(i);
    for(Re i=1;i<=4;++i) f[1][i]=-inf;
    for(Re i=1;i<=n;++i) b[i]=i;
    while(1){
        shuffle(b+2,b+n+1, rnd);
        for(Re i=2;i<=n;++i){
            for(Re k=0;k<=4;++k) f[i][k]=-inf;
            int x=b[i];
            int cnt = 0;
            for(Re j=1;j<i;++j)
                if(dis[b[j]][x]<=K)
                    for(Re k=1;k<=4;++k){
                        f[i][k]=max(f[i][k],f[j][k-1]);
                        ++cnt;
                        if (cnt < 10) continue;
                        cnt = 0;
                        ed=clock();
                        if(ed-st>1900000){ 
                            // if(dis[1][x]<=K) ans=max(ans,f[i][4]+a[x]);
                            ot(ans); 
                            return 0; 
                        }
                    }
            for(Re k=0;k<=4;++k) f[i][k]+=a[x];
            if(dis[1][x]<=K) ans=max(ans,f[i][4]);
        }
        // for(Re i=1;i<=n;++i) ot(b[i]),_;el;
        // for(Re i=1;i<=n;++i) ot(f[i][0]),_;el;
        // for(Re i=1;i<=n;++i) ot(f[i][1]),_;el;
        // for(Re i=1;i<=n;++i) ot(f[i][2]),_;el;
        // for(Re i=1;i<=n;++i) ot(f[i][3]),_;el;
        // for(Re i=1;i<=n;++i) ot(f[i][4]),_;el;
    }
}