class Solution {
public:
    long long dfs(vector<vector<int>>& adj,int cur,int par,
                   vector<int>& price, vector<map<int,long long>>& dp)
    {
        if(dp[cur].count(par)) return dp[cur][par];
        long long ans=0;
        for(auto i:adj[cur]){
            if(i==par) continue;
            ans=max(ans,dfs(adj,i,cur,price,dp));
        }
        dp[cur][par]=(ans+price[cur]);
        return dp[cur][par];
    }
    long long maxOutput(int n, vector<vector<int>>& edges, vector<int>& price) {
       vector<vector<int>> adj(n);
       for(auto &i: edges){
           adj[i[0]].push_back(i[1]);
           adj[i[1]].push_back(i[0]);
       }
       vector<map<int,long long>> dp(n);
       long long ans=0;
       for(int i=0;i<n;i++){
           if(adj[i].size()==1){
              //make i as root, get the ans and maximise that
              long long temp=dfs(adj,i,-1,price,dp)-price[i];
              ans=max(ans,temp);
           }
       }
       return ans;
    }
};



/*
given n nodes [0,n-1], prices of n nodes, undirected and unrooted and non cyclic tree, tak any node as root and find max price sum - min price sum and maximise this.

brute force->
take each node as root and find max - price of root and maximise this , but problem is this will take O(n^2) time,
opti-1: when finding answers for any particluar root we will be exploring all of its childrens als but we can't use that answers stored why?
-> beacuse that will be giving the answers of that particluar subtree while subtree is also changing.

so it depends on who is calling which node.

op-1: brute force -> O(n^2)
op-2: storing answers for each root -> not covering the whole subtree
op-3: store who had called whom
op-4: make root only those who has one childrens only, that will maximise that




*/