rt

感觉像 $O(n^3)$，但随机数据跑得飞快，洛谷上过了，求hack

#include<bits/stdc++.h>
#define sto using
#define zdc namespace
#define orz std;
sto zdc orz
#define int long long
const int INF=4e18;
int n,m,k,a[1000005],tot,head[1000005],ans=-INF;
bool vis[2505][2505];
vector<int> to[2505],canto[2505];//to[i]表示第i个点开始能到的点，canto[i]表示从哪些点开始能到第i个点 
struct edge{
	int to,next;
}e[1000005];
struct node{
	int id,x;
};
void add(int x,int y){
	tot++;
	e[tot].next=head[x];
	e[tot].to=y;
	head[x]=tot;
	return;
}
void bfs(int st){
	queue<node> q;
	q.push(node{st,0});
	while(q.empty()==false){
		node cur=q.front();
		q.pop();
		for(int i=head[cur.id]; i; i=e[i].next){
			int nxt=e[i].to;
			if(vis[st][nxt]==false&&cur.x<k){
				vis[st][nxt]=true;
				q.push(node{nxt,cur.x+1});
			}
		}
	}
}
bool f[1000005];
bool cmp(int x,int y){
	return a[x]>a[y];
}
signed main(){
//	freopen("holiday.in","r",stdin);
//	freopen("holiday.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>k;
	k++;
	for(int i=2; i<=n; i++)
		cin>>a[i];
	for(int i=1; i<=m; i++){
		int x,y;
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	for(int i=1; i<=n; i++)
		bfs(i);
//	for(int i=1; i<=n; i++,cout<<'\n')
//		for(int j=1; j<=n; j++)
//			cout<<vis[i][j]<<' ';
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			if(vis[i][j]==true)
				to[i].push_back(j),canto[j].push_back(i);
	for(int i=1; i<=n; i++)
		sort(to[i].begin(),to[i].end(),cmp),sort(canto[i].begin(),canto[i].end(),cmp);
	f[1]=true;
	for(int B=1; B<=n; B++){
		if(f[B]==true)
			continue;
		f[B]=true;
		for(int i=0; i<to[B].size(); i++){
			int C=to[B][i];
			if(f[C]==true)
				continue;
			f[C]=true;
			int maxi=-INF,MAXI=-INF,maxi2=-INF,MAXI2=-INF,pos=0,POS=0;
			for(int j=0; j<to[1].size(); j++){
				int A=to[1][j];
				if(f[A]==true||vis[A][B]==false)
					continue;
				if(maxi<a[A])
					pos=A,MAXI=maxi,maxi=a[A];
				else
					MAXI=max(MAXI,a[A]);
				if(maxi!=-INF&&MAXI!=-INF)
					break;
			}
			for(int j=0; j<canto[1].size(); j++){
				int D=canto[1][j];
				if(f[D]==true||vis[C][D]==false)
					continue;
				if(maxi2<a[D])
					POS=D,MAXI2=maxi2,maxi2=a[D];
				else
					MAXI2=max(MAXI2,a[D]);
				if(maxi2!=-INF&&MAXI2!=-INF)
					break;
			}
//			cout<<pos<<' '<<B<<' '<<C<<' '<<POS<<'\n';
//			cout<<a[B]<<' '<<a[C]<<' '<<maxi<<' '<<maxi2<<'\n';
			if(POS!=pos&&C!=B&&B!=POS&&C!=POS&&C!=pos&&B!=pos)
				ans=max(ans,a[B]+a[C]+maxi+maxi2);
			else
				ans=max(ans,a[B]+a[C]+maxi+max(MAXI,MAXI2)); 
			f[C]=false;
		}
		f[B]=false;
	}
	f[1]=false;
	cout<<ans;
	return 0;
}