• + 0 comments

    Can some one help me out by explaining why my code fails?

    #include<bits/stdc++.h>
    #define lld      long
    #define mp       make_pair
    #define pb       push_back
    #define ff       first
    #define ss       second
    #define pll      pair<lld,lld>
    #define pii      pair<int,int>
    #define vll      vector<lld>
    #define vii      vector<int>
    #define umap     unordered_map
    #define lb       lower_bound
    #define ub       upper_bound
    #define mod      1000000007
    #define all(x)   x.begin(),x.end()
    #define sort1(x) sort(x,greater<int>())
    #define rep(i,a,b) for(i = a; i < b; i++)
    #define fio      ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
    using namespace std;
    
    namespace forever {
        template<class type1,class type2>
            inline istream &operator>>(istream &in,pair<type1,type2> &p)
            {
                in>>p.ff>>p.ss;
                return in;
            }
        template<class type1,class type2>
            inline ostream &operator<<(ostream &o,pair<type1,type2> &p)
            {
                 o<<"("<<p.ff<<","<<p.ss<<")";
                return o;
            } 
        template<class type>
            inline ostream &operator<<(ostream &o,vector<type> &v)
            {
                for(int i=0;i<v.size();i++)
                    o<<v[i]<<" ";
                return o;    
            }
        template<class t>
            inline istream &operator>>(istream &in,vector<t> &p)
            {
                for(auto & x : p)
                    in >> x;
                return in;
            }
        struct custom_hash {
            static uint64_t splitmix64(uint64_t x) {
                x += 0x9e3779b97f4a7c15;
                x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
                x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
                return x ^ (x >> 31);
            }
            size_t operator()(uint64_t x) const {
                static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
                return splitmix64(x + FIXED_RANDOM);
            }
        };
    }
    using namespace forever;
    struct comp{
        bool operator ()(pii const& a,pii const& b){
                return a.ss > b.ss;
        }
    };
    
    vii adj[100001];
    vii a(100001);
    priority_queue<pii,vector<pii>,comp> sr;
    umap<int,bool,custom_hash> vis;
    umap<int,int,custom_hash> level;
    int dfs(int u){
        int x=0,i;
        vis[u] = true;
        if(!adj[u].size()){   
            sr.push({u,a[u-1]});
            return a[u-1];
        }
        for(i=0;i<adj[u].size();i++){
            if(!vis[adj[u][i]] && level[adj[u][i]] >= level[u])
                x += dfs(adj[u][i]);
        }
        x += a[u-1];
        sr.push({u,x});
        return x;
    }
    
    
    void dfs1(int u){
        vis[u] = true;
        for(int i=0;i<adj[u].size();i++){
            if(!vis[adj[u][i]] && level[adj[u][i]]>=level[u])
                dfs1(adj[u][i]);
        }
    }
    void bfs(){
        int i,u = 1;
        queue<int> q;
        q.push(u);
        level[u] = 1;
        while(!q.empty()){
            u = q.front();
            vis[u] = true;
            q.pop();
            for(i=0;i<adj[u].size();i++){
                if(!vis[adj[u][i]]){
                    q.push(adj[u][i]);
                    level[adj[u][i]] = level[u] + 1;
                }
            }
        }
    }
    
    void test_cases(){
        int n,k,i,u,v;
        cin >> n >> k;
        a.resize(n);
        cin >> a;
        lld tsum = 0;
        for(int x: a){
            tsum += x;
        }
        //cout << tsum << "\n";
        for(i=0;i<n-1;i++){
            cin >> u >> v;
            adj[u].pb(v);
            adj[v].pb(u);
        }
        bfs();
        vis.clear();
        int te = dfs(1);
        vis.clear();
        /*while(!sr.empty()){
            cout << sr.top().ff << " " << sr.top().ss << "\n";
            sr.pop();
        }*/
        
        while(k-- && !sr.empty()){
            pii ram = sr.top();
            //cout << ram.ff << "\n";
            sr.pop();
            if(vis[ram.ff] || ram.ff==1){
                k++;
                continue;
            }
            //cout << "\n";
            if(ram.ss>-1)
                break;
            dfs1(ram.ff);    
            tsum -= ram.ss;
            //cout << tsum << "\n";
        }
        cout << tsum << "\n";
    }
    
    int main()
    {
        fio;     
        //#ifndef ONLINE_JUDGE 
        //freopen("ip.txt","r",stdin);
           //freopen("sout.txt","w",stdout);
        //#endif
        
        int  t=1;
        //cin >> t;
        while(t--){
            test_cases();
        }
        
        return 0;
    }