Subtask #1 #9 WA

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2600,W=200005,M=6250000;
int n,m,k,d[N][N],cnt,nxt[M],to[M],head[N],w[N],fcnt,fnxt[W],fto[W],fhead[N],ans,sum;
int mx[N],mxid[N],cmx[N],cmxid[N],tmx[N],tmxid[N],ish[N],u,v,vis[N],fx,fy;
void mem(){
	for(int i=1;i<=n;i++){
		vis[i]=0;
	}
}
void fadd(int u,int v){
	fto[++fcnt]=v;
	fnxt[fcnt]=fhead[u];
	fhead[u]=fcnt;
}
void add(int u,int v){
	to[++cnt]=v;
	nxt[cnt]=head[u];
	head[u]=cnt;
}
vector<int>A;
vector<int>B;
queue<int>q;
void bfs(int a){
	mem();
	q.push(a);d[a][a]=0;vis[a]=1;
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=fhead[x];i;i=fnxt[i]){
			int y=fto[i];
			if(vis[y]){
				continue;
			}
			vis[y]=1;
			d[a][y]=d[a][x]+1;
			q.push(y);
		}
	}
}
signed main(){
	scanf("%lld%lld%lld",&n,&m,&k);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			d[i][j]=INT_MAX;
		}
	}
	for(int i=2;i<=n;i++){
		scanf("%lld",&w[i]);
	}
	for(int i=1;i<=m;i++){
		scanf("%lld%lld",&u,&v);
		fadd(u,v);
		fadd(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++){
			if(i==j){
				continue;
			}
			if(d[i][j]<=k+1){
				add(i,j);
			}
		}
	}
	mem();
	for(int i=head[1];i;i=nxt[i]){
		int y=to[i];
		if(vis[y]){
			continue;
		}
		vis[y]=1;ish[y]=1;
		A.push_back(y);
	}
	mem();
	for(int j=0;j<A.size();j++){
		int x=A[j];
		for(int i=head[x];i;i=nxt[i]){
			int y=to[i];
			if(vis[y]||y==1){
				continue;
			}
			vis[y]=1;
			B.push_back(y);
		}
	}
	mem();
	for(int j=0;j<B.size();j++){
		int x=B[j];
		for(int i=head[x];i;i=nxt[i]){
			int y=to[i];
			if(ish[y]){
				if(w[y]>=mx[x]){
					tmxid[x]=cmxid[x];
					tmx[x]=cmx[x];
					cmxid[x]=mxid[x];
					cmx[x]=mx[x];
					mxid[x]=y;
					mx[x]=w[y];
				}
				else if(w[y]>=cmx[x]){
					tmxid[x]=cmxid[x];
					tmx[x]=cmx[x];
					cmxid[x]=y;
					cmx[x]=w[y];
				}
				else if(w[y]>=tmx[x]){
					tmxid[x]=y;
					tmx[x]=w[y];
				}
			}
		}
	}
	for(int i=0;i<B.size();i++){
		for(int j=0;j<B.size();j++){
			if(i==j||d[B[i]][B[j]]>k+1){
				continue;
			}
			sum=0;fx=fy=0;
			int x=B[i],y=B[j];
			if(mx[x]==mx[y]&&mx[y]==0){
				continue;
			}
			if(mxid[x]==y){
				fx=1;
				swap(mxid[x],cmxid[x]);swap(cmxid[x],tmxid[x]);
				swap(mx[x],cmx[x]);swap(cmx[x],tmx[x]);
			}
			if(cmxid[x]==y){
				fx=2;
				swap(cmxid[x],tmxid[x]);swap(cmx[x],tmx[x]);
			}
			if(mxid[y]==x){
				fy=1;
				swap(mxid[y],cmxid[y]);swap(cmxid[y],tmxid[y]);
				swap(mx[y],cmx[y]);swap(cmx[y],tmx[y]);
			}
			if(cmxid[y]==x){
				fy=2;
				swap(cmxid[y],tmxid[y]);swap(cmx[y],tmx[y]);
			}
			if(mxid[x]!=mxid[y]){
				ans=max(ans,mx[x]+w[x]+w[y]+mx[y]);
			}
			else{
				if(cmx[x]==cmx[y]&&cmx[y]==0){
					continue;
				}
				sum=max(mx[x]+cmx[y],cmx[x]+mx[y]);
				ans=max(ans,sum+w[x]+w[y]);
			}
			if(fx==1){
				swap(cmxid[x],tmxid[x]);swap(mxid[x],cmxid[x]);
				swap(cmx[x],tmx[x]);swap(mx[x],cmx[x]);
			}
			if(fx==2){
				swap(cmxid[x],tmxid[x]);swap(cmx[x],tmx[x]);
			}
			if(fy==1){
				swap(cmxid[y],tmxid[y]);swap(mxid[y],cmxid[y]);
				swap(cmx[y],tmx[y]);swap(mx[y],cmx[y]);
			}
			if(fy==2){
				swap(cmxid[y],tmxid[y]);swap(cmx[y],tmx[y]);
			}
		}
	}
	printf("%lld",ans);
	return 0;
}