# Codeforces Problem

``````
#include<bits/stdc++.h>
#define ll long long int
#define pb push_back
#define vi vector<ll>
#define vb vector<bool>
#define vd vector<double>
#define vc vector<char>
#define vii vector<vi>
#define mp make_pair
#define vpi vector< pair<ll,ll> >
#define take_input freopen("input.txt", "r", stdin)
#define give_output freopen("output.txt", "w", stdout)
#define fastIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define fi first
#define se second
#define mod 1000000007
#define min_pql priority_queue< ll, vector<ll>, greater<ll> >

using namespace std;
using namespace std::chrono;

struct val{
mutable int deg=0;
ll wgt=0;

bool operator<(const val& t) const{
if(this->deg != t.deg){
return (this->deg > t.deg);
}
return (this->wgt > t.wgt);
}
};

int main(){
fastIO;
// take_input;
// give_output;
int t; cin >> t;
while(t--){
int n; cin >> n;
ll sum=0;
vector<val> a(n+1);
for(int i=1; i<=n; i++){
ll num; cin >> num;
a[i].wgt = num;
sum += a[i].wgt;
}
for(int i=1; i<n; i++){
int n1, n2; cin >> n1 >> n2;
a[n1].deg++; a[n2].deg++;
}
sort(a.begin(), a.end());
// for(auto p:a) cout << p.deg << " " << p.wgt << endl;
// cout << endl;
cout << sum << " ";
for(int i=0; i<=n; i++){
while(a[i].deg>1){
a[i].deg--;
sum += a[i].wgt;
cout << sum << " ";
}
}
cout << endl;
}
}
``````

I was trying this question from codeforces. The problem is pretty simple but I am getting WA for test case 2. I saw tutorial also and they had told the same approach as mine. So if some one could figure out which part I am doing wrong please help me. Thanks in advance

@suman_18733097 give this a try too

BIGGG Problem Statement and I tend to become unconscious whenever I see graph problems.

Yeah but if you have time please give it a try. It is simple…its just that I am doing some minor implementation mistake and not able to get what

Mistake is you always took the maximum degree node whereas you have to choose node with greater than k degree and maximum value.
Check on this case–
1
6
1 2 3 4 5 120
1 5
2 6
5 6
3 5
4 5
Still stuck feel free to ask…!!

1 Like

I knew that I am messing some very small thing. By the way thanks.