其余AC

#include <bits/stdc++.h>
using namespace std;

const int N = 2510;
typedef pair<int, int> PII;
typedef long long LL;
struct Ans
{
	int a, b;
	LL w;
} mx[N], smx[N], tmx[N];
int n, m, k, vis[N];
LL ls[N];
vector<int> g[N], gt[N];
vector<Ans> ans;

void bfs(int x)
{
	memset(vis, false, sizeof(vis));
	queue<PII> q;
	q.push({x, -1});
	while(q.size())
	{
		int at = q.front().first, num = q.front().second; q.pop();
		if(vis[at]) continue;
		if(num > k) continue;
		vis[at] = true;
		if(at != x) gt[x].push_back(at);
		for(int i = 0; i < g[at].size(); i++) q.push({g[at][i], num+1});
	}
}

signed main()
{
	//freopen("holiday.in", "r", stdin);
	//freopen("holiday.out", "w", stdout);
	ios::sync_with_stdio(false);
	scanf("%d %d %d", &n, &m, &k);
	for(int i = 2; i <= n; i++) scanf("%lld", &ls[i]);
	while(m--)
	{
		int u, v;
		scanf("%d %d", &u, &v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i = 1; i <= n; i++) bfs(i);
	for(int i = 0; i < gt[1].size(); i++)
	{
		int a = gt[1][i];
		for(int j = 0; j < gt[a].size(); j++)
		{
			int b = gt[a][j];
			if(a == b || b == 1) continue;
			LL w = ls[a] + ls[b];
			if(w > mx[b].w)
			{
				tmx[b] = smx[b];
				smx[b] = mx[b];
				mx[b] = {a, b, w};
			}
			else if(w > smx[b].w)
			{
				tmx[b] = smx[b];
				smx[b] = {a, b, w};
			}
			else if(w > tmx[b].w) tmx[b] = {a, b, w};
		}
	}
	LL w = 0;
	for(int i = 2; i <= n; i++)
	{
		for(int j = 0; j < gt[i].size(); j++)
		{
			int j1 = gt[i][j];
			if(j1 == 1) continue;
			Ans a1 = mx[i], a2 = smx[i], a3 = tmx[i], b1 = mx[j1], b2 = smx[j1], b3 = tmx[j1];
			if(a1.a != b1.a && a1.a != b1.b && a1.b != b1.a) w = max(w, a1.w + b1.w);
			if(a2.a != b1.a && a2.a != b1.b && a2.b != b1.a) w = max(w, a2.w + b1.w);
			if(a3.a != b1.a && a3.a != b1.b && a3.b != b1.a) w = max(w, a3.w + b1.w);
			if(a1.a != b2.a && a1.a != b2.b && a1.b != b2.a) w = max(w, a1.w + b2.w);
			if(a2.a != b2.a && a2.a != b2.b && a2.b != b2.a) w = max(w, a2.w + b2.w);
			if(a3.a != b2.a && a3.a != b2.b && a3.b != b2.a) w = max(w, a3.w + b2.w);
			if(a1.a != b3.a && a1.a != b3.b && a1.b != b3.a) w = max(w, a1.w + b3.w);
			if(a2.a != b3.a && a2.a != b3.b && a2.b != b3.a) w = max(w, a2.w + b3.w);
			if(a3.a != b3.a && a3.a != b3.b && a3.b != b3.a) w = max(w, a3.w + b3.w);
		}
	}
	printf("%lld\n", w);
	return 0;
}