Untitled
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