3965. Finish Time of Tasks I

You are given an integer n representing the number of tasks in a project, numbered from 0 to n - 1. These tasks are connected as a tree rooted at task 0. This is represented by a 2D integer array edges of length n - 1, where edges[i] = [u_i, v_i] indicates that task u_i is the parent of task v_i.

You are also given an array baseTime of length n, where baseTime[i] represents the time to complete task i.

The finish time of each task is calculated as follows:

• Leaf task: The finish time is baseTime[i].
• Non-leaf task:
  • Let earliest be the minimum finish time among its children, and latest be the maximum finish time among its children.
  • Let ownDuration be (latest - earliest) + baseTime[i].
  • The finish time of task i is latest + ownDuration.

Return the finish time of the root task 0.

class Solution {
    long long dfs(vector<vector<int>>& adj, int u, int par, vector<int>& A) {
        long long mi = LLONG_MAX, ma = LLONG_MIN;
        for(auto& v : adj[u]) {
            if(v == par) continue;
            long long sub = dfs(adj,v,u,A);
            mi = min(mi, sub);
            ma = max(ma, sub);
        }
        if(mi == LLONG_MAX) return A[u];
        return A[u] + (ma - mi) + ma;
    }
public:
    long long finishTime(int n, vector<vector<int>>& edges, vector<int>& baseTime) {
        vector<vector<int>> adj(n);
        for(auto& e : edges) {
            int u = e[0], v = e[1];
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        return dfs(adj,0,-1,baseTime);
    }
};