Untitled

 avatar
unknown
plain_text
2 years ago
885 B
4
Indexable
class Solution {
public:
    long long dfs(int i,vector<int>& values, int par,vector<vector<int>>&adj){ // we are picking which node to pick
        if(adj[i].size()==1 && i!=0) return values[i]; //if its the leaf return its value
        long long sum=0;
        for(auto nbr:adj[i]){
            if(nbr==par) continue;
            sum+= dfs(nbr,values,i,adj);
        }
        return min(1LL*values[i],sum); // else return the minvalue of node value and sum of its child value
    }

    long long maximumScoreAfterOperations(vector<vector<int>>& edges, vector<int>& values) {
        vector<vector<int>>adj(edges.size()+1);
        for(auto i:edges){
            adj[i[0]].push_back(i[1]);
            adj[i[1]].push_back(i[0]);
        }
        long long totsum=0;
        for(auto i:values) totsum+=i;
        return totsum - dfs(0,values,-1,adj);
    }
};
Editor is loading...
Leave a Comment