45pts WA求调 悬关

#include <bits/stdc++.h>
using namespace std;
int n,m,k,u,v,a[2505],dis[2505],ans;
bool t[2505][2505];
vector<int>G[2505],f[2505];
bool cmp(int x,int y){
	return a[x]>a[y];
}
void bfs(int x) {
    memset(dis,-1,sizeof(dis));
    queue<int>q;
    q.push(x);
    dis[x]=0;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        if(u!=x){
            t[x][u]=1;
            if(x!=1&&t[1][u]){
                f[x].push_back(u);
                sort(f[x].begin(), f[x].end(),cmp);
                if(f[x].size()>3) f[x].pop_back();
            }
        }
        if(dis[u]==k+1) continue;
        for (int v:G[u]) if(dis[v]==-1){
            dis[v]=dis[u]+1;
            q.push(v);
        }
    }
}
int main(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=2;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++){
		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 b=2;b<=n;b++) for(int c=2;c<=n;c++) if(t[b][c])
        for(int a1:f[b]) for(int d:f[c]) if(a1!=c&&b!=d&&a1!=d) ans=max(ans,a[a1]+a[b]+a[c]+a[d]);
	cout<<ans;
	return 0;
}