4015. Weighted Sum of a Tree

You are given an integer array parent of length n representing a rooted tree with nodes labeled from 0 to n - 1.

The tree is rooted at node 0, so parent[0] = -1. For each node i where 1 <= i <= n - 1, parent[i] denotes the parent of node i.

You are also given an integer array nums of length n, where nums[i] denotes the value of node i.

The weight of a node i at depth d is nums[i] * (h - d + 1), where h is the height of the tree.

Return the sum of the weights of all nodes in the tree.

The depth of a node is the number of nodes on the path from the root to that node, inclusive, with the root having depth 1.

The height of the tree is the maximum depth among all nodes in the tree.

class Solution {
    long long dfs(vector<vector<int>>& adj, int u, long long h) {
        long long res = h;
        for(auto& v : adj[u]) {
            res = max(res,dfs(adj,v,h+1));
        }
        return res;
    }
    long long dfs1(vector<vector<int>>& adj, int u, int d, int h, vector<int>& A) {
        long long res = 1ll * (h - d + 1) * A[u];
        for(auto& v : adj[u]) {
            res += dfs1(adj,v,d+1,h,A);
        }
        return res;
    }
public:
    long long weightedSum(vector<int>& parent, vector<int>& nums) {
        int n = parent.size();
        vector<vector<int>> adj(n);
        for(int i = 1; i < n; i++) adj[parent[i]].push_back(i);
        long long h = dfs(adj,0,0);
        return dfs1(adj,0,0,h,nums);
    }
};