记录编号	589105	评测结果	WWWWWWWWWWWWEEEWWEEE
题目名称	派蒙的树	最终得分	0
用户昵称	Untitled	是否通过	未通过
代码语言	C++	运行时间	5.719 s
提交时间	2024-07-03 14:30:29	内存使用	7.37 MiB

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

int const N=310;
int T,n,idx,len,a[N];
int head[N],Next[N],ver[N];
bool d[N];
long long res;

void edge(int a,int b){
    Next[++idx]=head[a],head[a]=idx,ver[idx]=b;
    Next[++idx]=head[b],head[b]=idx,ver[idx]=a;
    return;
}

struct node{
    int x,s;
};

int bfs(int x){
    memset(d,0,sizeof(d));
    len=0;
    int p;
    queue<node> q;
    q.push(node{x,0});
    int u;
    node t;
    while (q.size()){
        t=q.front();q.pop();
        u=t.x;
        d[u]=1;
        for (int i=head[u];i;i=Next[i]){
            if (d[ver[i]]) continue;
            q.push(node{ver[i],t.s+1});
        }
        if (len<t.s) len=t.s,p=u;
    }
    return p;
}

int main(){
    freopen("Paimon.in","r",stdin);
    freopen("Paimon.out","w",stdout);
    
    int u,v;
    scanf("%d",&T);
    for (int x=1;x<=T;x++){
        res=0;
        memset(head,0,sizeof(head));
        memset(Next,0,sizeof(Next));
        memset(ver,0,sizeof(ver));
        idx=0;
        scanf("%d",&n);
        for (int i=1;i<=n;i++) scanf("%d",&a[i]);
        for (int i=1;i<=n;i++){
            scanf("%d %d",&u,&v);
            edge(u,v);
        }
        bfs(bfs(1));
        sort(a+1,a+n+1);reverse(a+1,a+n+1);
        for (int i=1;i<=len;i++) res+=(long long)a[i];
        printf("%lld\n",res);
    }
    
    return 0;
}