Wa 了一个，T 了一堆 65pts

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 2600;
ll n,m,k;
ll r[N];
vector<ll> vec[N];
ll dis[N][N];
void dfs(ll id,ll topo,ll step){
	dis[id][topo] = step;
	for(auto v : vec[id]){
		if(dis[v][topo]<step+1) continue;
		dfs(v,topo,step+1);
	}
}
ll res[N][N];
struct Node{
	ll val,id;
	bool operator <(const Node &b) const{
		return val>b.val;
	}
};
vector<Node> sol[N];
#define IsAble(a,b,c,d) (a!=b&&b!=c&&c!=d&&a!=c&&b!=d&&a!=d&&dis[b][c]<=k)
ll calc(ll x,ll y){
	//sol[x] sol[y]
	ll det = 0;
	if(sol[x].size()>=1&&sol[y].size()>=1){
		if(IsAble(sol[x][0].id,x,y,sol[y][0].id)){
			det = max(det,sol[x][0].val+sol[y][0].val);
		}
	}
	if(sol[x].size()>=1&&sol[y].size()>=2){
		if(IsAble(sol[x][0].id,x,y,sol[y][1].id)){
			det = max(det,sol[x][0].val+sol[y][1].val);
		}
	}
	if(sol[x].size()>=2&&sol[y].size()>=1){
		if(IsAble(sol[x][1].id,x,y,sol[y][0].id)){
			det = max(det,sol[x][1].val+sol[y][0].val);
		}
	}
	if(sol[x].size()>=2&&sol[y].size()>=2){
		if(IsAble(sol[x][1].id,x,y,sol[y][1].id)){
			det = max(det,sol[x][1].val+sol[y][1].val);
		}
	}
	return det;
}
int main(){
	scanf("%lld%lld%lld",&n,&m,&k);
	for(ll i = 2; i <= n; i++){
		scanf("%lld",&r[i]);
	}
	for(ll i = 1; i <= m; i++){
		ll u,v;
		scanf("%lld%lld",&u,&v);
		vec[u].push_back(v);
		vec[v].push_back(u);
	}
	memset(dis,0x3f,sizeof(dis));
	for(ll i = 1; i <= n; i++){
		dfs(i,i,-1);
	}
	/*
	for(ll i = 1; i <= n; i++){
		for(ll j = 1; j <= n; j++){
			printf("%lld ",dis[i][j]);
		}
		puts("");
	}
	*/
	for(ll a = 2; a <= n; a++){
		for(ll b = 2; b <= n; b++){
			if(a==b||dis[a][b]>k||dis[1][a]>k) continue;
			res[a][b] = r[a]+r[b];
			sol[b].push_back((Node){res[a][b],a});
			//printf("1->%lld->%lld    res = %lld\n",a,b,res[a][b]);
		}
	}
	ll ans = 0;
	for(ll i = 2; i <= n; i++) sort(sol[i].begin(),sol[i].end());
	for(ll b = 2; b <= n; b++){
		for(ll c = 2; c <= n; c++){
			if(b==c) continue;
			//sol[b][]
			//sol[c][]
			ans = max(ans,calc(b,c));
		}
	}
	printf("%lld\n",ans);
	return 0;
}

就是枚举配对的 $1-a-b$ 和 $1-c-d$

这不应该是 $n^2$ 吗