https://www.luogu.com.cn/record/174437836

#include<bits/stdc++.h>
using namespace std;
const int N = 2505;
const int M = 2e4+5;
struct node
{
	int to;
	int nxt;
}t[M];
int cnt;
int head[N];
int d[N][N];
long long a[N];
int s[N][N];
int r[N][4];
signed main()
{
	int n,m,k;
	scanf("%d %d %d",&n,&m,&k);
	for(int i = 2;i<=n;i++)
	{
		scanf("%lld",&a[i]);
	}
	for(int i = 1;i<=m;i++)
	{
		int x,y;
		scanf("%d %d",&x,&y);
		t[++cnt].to = y;
		t[cnt].nxt = head[x];
		head[x] = cnt;
		t[++cnt].to = x;
		t[cnt].nxt = head[y];
		head[y] = cnt;
	}
	memset(d,0x3f,sizeof(d));
	for(int i = 1;i<=n;i++)
	{
		d[i][i] = 0;
		queue<int>q;
		q.push(i);
		while(q.size())
		{
			int x = q.front();
			q.pop();
			for(int j = head[x];j;j = t[j].nxt)
			{
				int v = t[j].to;
				if(d[i][v]>d[i][x]+1)
				{
					d[i][v] = d[i][x]+1;
					q.push(v);
				}
			}
		}
	}
	for(int i = 1;i<=n;i++)
	{
		int num = 0;
		for(int j = 1;j<=n;j++)
		{
			if(d[i][j]-1<=k&&i!=j)
			{
				s[i][++num] = j;
			}
		}
		s[i][0] = num;
	}
	for(int i = 1;i<=n;i++)
	{
		int num[n+5] = {};
		for(int j = 1;j<=s[i][0];j++)
		{
			num[s[i][j]]++;
		}
		for(int j = 1;j<=s[1][0];j++)
		{
			num[s[1][j]]++;
		}
		int maxx = 0;
		int maxxx = 0;
		for(int j = 1;j<=n;j++)
		{
			if(num[j] == 2&&j!=i)
			{
				if(maxx<a[j])
				{
					maxx = a[j];
					maxxx = j;
				}
			}
		}
		int maxx1 = 0,maxxx1 = 0;
		for(int j = 1;j<=n;j++)
		{
			if(num[j] == 2&&j!=i&&j!=maxxx)
			{
				if(maxx1<a[j])
				{
					maxx1 = a[j];
					maxxx1 = j;
				}
			}
		}
		int maxx2 = 0,maxxx2 = 0;
		for(int j = 1;j<=n;j++)
		{
			if(num[j] == 2&&j!=i&&j!=maxxx1&&j!=maxxx)
			{
				if(maxx2<a[j])
				{
					maxx2 = a[j];
					maxxx2 = j;
				}
			}
		}
		int maxx3 = 0,maxxx3 = 0;
		for(int j = 1;j<=n;j++)
		{
			if(num[j] == 2&&j!=i&&j!=maxxx1&&j!=maxxx&&j!=maxxx2)
			{
				if(maxx3<a[j])
				{
					maxx3 = a[j];
					maxxx3 = j;
				}
			}
		}
		r[i][0] = maxxx;
		r[i][1] = maxxx1;
		r[i][2] = maxxx2;
		r[i][3] = maxxx3;
	}
	long long ans = 0;
	for(int B = 1;B<=n;B++)
	{
		for(int C = 1;C<=n;C++)
		{
			if(B == C||d[B][C]-1>k)
			{
				continue;
			}
			for(int i = 0;i<4;i++)
			{
				for(int j = 0;j<4;j++)
				{
					int A = r[B][i];
					int D = r[C][j];
					if(A == B||A == C||A == D||B == C||B == D||C == D||A == 0||D == 0)
					{
						continue;
					}
					ans = max(ans,a[A]+a[B]+a[C]+a[D]);
				}
			}
		}
	}
	printf("%lld",ans);
	return 0;
}