思路跟正解一样（应该），民间数据90（10月30日），官方数据45，直接爆炸

#include<bits/stdc++.h>
#define int long long
const int N = 3005;
const int M = 100005;

using namespace std;

int n, m, k;
int v[N];

int head[N], cnt;

struct stu{
	int u, v;
	int next;
} edge[M];

void add(int u, int v)
{
	edge[++cnt]=(stu){u, v, head[u]};
	head[u]=cnt;
}

int a[N][N];
int f[N][N];
queue<int> que;
bool vis[N];

void bfs(int s)
{
	while(que.size()) que.pop();
	memset(vis, 0, sizeof(vis));
	que.push(s);vis[s]=1;
	while(que.size())
	{
		int u=que.front();
		que.pop();
		for(int i=head[u]; i; i=edge[i].next)
		{
			int v=edge[i].v;
			if(vis[v]) continue;
			vis[v]=1, que.push(v), f[s][v]=f[s][u]+1;
		}
	}
}

int b[N], c[N], d[N], p[N], q[N], r[N];
int ans;

signed main()
{
	// freopen("holiday.in", "r", stdin);
	// freopen("holiday.out", "w", stdout);
	scanf("%lld%lld%lld", &n, &m, &k);
	k++;
	for(int i=2; i<=n; i++) scanf("%lld", &v[i]);
	memset(a, 0x3f, sizeof(a));
	for(int i=1; i<=n; i++) a[i][i]=0;
	for(int i=1; i<=m; i++)
	{
		int u, v;
		scanf("%lld%lld", &u, &v);
		a[u][v]=a[v][u]=1;
		add(u, v), add(v, u);
	}
	for(int i=1; i<=n; i++) bfs(i);
//	for(int i=1; i<=n; i++)
//	{
//		for(int j=1; j<=n; j++)
//			printf("%lld ", f[i][j]==0x3f3f3f3f?-1:f[i][j]);
//		printf("\n");
//	}
	for(int i=2; i<=n; i++)
		for(int j=2; j<=n; j++)
		{
			if(i==j) continue;
			if(f[1][i]<=k&&f[i][j]<=k)
			{
				int val=v[i]+v[j];
				if(b[j]<=val) d[j]=c[j], c[j]=b[j], b[j]=val, r[j]=q[j], q[j]=p[j], p[j]=i;
				else if(c[j]<val) d[j]=c[j], c[j]=val, r[j]=q[j], q[j]=i;
				else if(d[j]<val) d[j]=val, r[j]=i;
			}
		}
//	for(int i=1; i<=n; i++)
//		printf("%lld %lld  %lld %lld  %lld %lld\n", b[i], p[i], c[i], q[i], d[i], r[i]);
	
	for(int i=1; i<=n; i++)
		for(int j=i+1; j<=n; j++)
			if(f[i][j]<=k)
			{
				if(p[i]!=p[j]&&p[i]!=j&&i!=p[j]) ans=max(ans, b[i]+b[j]);
				if(p[i]!=q[j]&&p[i]!=j&&i!=q[j]) ans=max(ans, b[i]+c[j]);
				if(p[i]!=r[j]&&p[i]!=j&&i!=r[j]) ans=max(ans, b[i]+d[j]);
				if(q[i]!=p[j]&&q[i]!=j&&i!=p[j]) ans=max(ans, c[i]+b[j]);
				if(q[i]!=q[j]&&q[i]!=j&&i!=q[j]) ans=max(ans, c[i]+c[j]);
				if(q[i]!=r[j]&&q[i]!=j&&i!=r[j]) ans=max(ans, c[i]+d[j]);
				if(r[i]!=p[j]&&r[i]!=j&&i!=p[j]) ans=max(ans, d[i]+b[j]);
				if(r[i]!=q[j]&&r[i]!=j&&i!=q[j]) ans=max(ans, d[i]+c[j]);
				if(r[i]!=r[j]&&r[i]!=j&&i!=r[j]) ans=max(ans, d[i]+d[j]);
			}
	
	printf("%lld", ans);
	
	return 0;
}