#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
and I tend to become unconscious whenever I see graph problems.