树形 DP
6419. 使二叉树所有路径值相等的最小代价 - 力扣（LeetCode）
在这道题目当中, 要求从根节点到叶子结点的路径值相同, 也就是要求每棵子树分别到其左右子树的路径值相等, 设一棵以 x 为根节点的子树, 这个子树含有叶子结点 a 和 b, 那么cost(root−>a)=cost(root−>b)
即
cost(root−>x)+cost(x−>a)−cost[x]=cost(root−>x)+cost(x−>b)−cost[x]
, 即 cost(x−>a)=cost(x−>b)
也就是说, 递归遍历 root 中的所有子树, 通过一些操作使每棵子树到其两个叶子结点的路径值相同就可以了, f(u) 表示以 u 为根节点的子树到其叶子节点的路径值的最大值, f(u)=max(f(l),f(r)), 操作的代价为 max(f(l),f(r))−min(f(l),f(r))
class Solution { public: int minIncrements(int n, vector<int>& cost) { int res=0; function<int(int)> dfs=[&](int u){ int l=2*u, r=2*u+1; if(l>n){ return cost[u-1]; } int l_cost=dfs(l); // 左子树路径值的最大值 int r_cost=dfs(r); // 右子树路径值的最大值 res+=max(l_cost, r_cost)-min(l_cost, r_cost); return max(l_cost, r_cost)+cost[u-1]; }; int root_cost=dfs(1); return res; } };
