#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
vector<vector<ll>> G,aux;
ll val[1010];
ll dfs(int node,int pad){
ll ans=val[node];
for(auto i:aux[node]){
if(i==pad)continue;
ans=max(ans,dfs(i,node));
}
return ans;
}
int main(){
int n;
vector<ii> v;
ll a,b;
cin>>n;
for(int i=1;i<=n;i++){
cin>>val[i];
v.push_back(ii(val[i],i));
}
sort(v.rbegin(),v.rend());
G.assign(n+2,vector<ll>());
for(int i=0;i<n-1;i++){
cin>>a>>b;
G[a].push_back(b);
G[b].push_back(a);
}
// cout<<123<<endl;
ll ans=0;
for(int i=0;i<n;i++){
aux=G;
vector<vector<ll>> gg;
for(int j=0;j<aux[v[i].second].size();j++){
ans+=v[i].first;
ans+=dfs(aux[v[i].second][j],v[i].second);
}
//cout<<ans<<endl;
gg.push_back(vector<ll>());
for(int j=1;j<=n;j++){
gg.push_back(vector<ll>());
//cout<<123<<endl;
for(int l=0;l<aux[j].size();l++){
//cout<<aux[j][l]<<" "<<v[i].second<<endl;
//cout<<123<<endl;
if(aux[j][l]==v[i].second)continue;
// cout<<gg[j].size()<<endl;
gg[j].push_back(aux[j][l]);
}
}
// cout<<123<<endl;
gg[v[i].second].clear();
G=gg;
}
cout<<ans<<endl;
}
Compilation message
sjekira.cpp: In function 'int main()':
sjekira.cpp:37:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for(int j=0;j<aux[v[i].second].size();j++){
| ~^~~~~~~~~~~~~~~~~~~~~~~~
sjekira.cpp:46:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for(int l=0;l<aux[j].size();l++){
| ~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
0 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
2 ms |
620 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
0 ms |
364 KB |
Output is correct |
6 |
Correct |
75 ms |
620 KB |
Output is correct |
7 |
Correct |
52 ms |
492 KB |
Output is correct |
8 |
Correct |
36 ms |
492 KB |
Output is correct |
9 |
Correct |
67 ms |
492 KB |
Output is correct |
10 |
Correct |
74 ms |
584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
0 ms |
364 KB |
Output is correct |
6 |
Runtime error |
2 ms |
620 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
7 |
Halted |
0 ms |
0 KB |
- |