来水一发春赛个人赛最后一题的题解QWQ

算法：树形DP + 贪心 O(n)

通过思考，我们可以得到大致的贪心思路：

1. 如果我们想要时间更加使用的少，就要增加并行时间（两个处理器同时工作）。
2. 我们可以通过调整左右子树的权值（因为子树互不干涉）来使答案更优（左右子树仍需遵循拓扑序）。

这就启发了我们维护两个权值，总时间（串行+并行）和串行时间（只能一个处理器工作）。对于一个节点，我们可以通过调度左子树和右子树的串行时间来使答案更优。

接下来我们分情况讨论：

1.左串行时间 > 右边总时间 （右串行时间 > 左总时间 类似）
我们总是可以通过左右开工的方式，使最后根节点的串行时间 = 左串行 - 右边总时间（且一定最优）。

2.左串行时间 <= 右边总时间 && 右边串行时间 <= 左边总时间
那么我们可以通过左右开工的方式，使最后串行时间 = 0.

最后我们输出答案就可以了 总时间 / 2 + 只能串行的时间 / 2 。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
#define pdd pair<double,double>

class Solution {
public:

    pdd calc(pdd a,pdd b)
    {
        pdd res;
        res.first = a.first + b.first;
        res.second = 0;

        if(b.second > a.first)
        {
            res.second = b.second - a.first;
            return res;
        }

        if(a.second > b.first)
        {
            res.second = a.second - b.first;
            return res;
        }

        return res;
    }

    pdd dfs(TreeNode *root)
    {
        if(root == NULL) return {0,0};
        pdd res = calc(dfs(root->left),dfs(root->right));
        res.first += root -> val;
        res.second += root -> val;
        return res;
    }
    double minimalExecTime(TreeNode* root) {
        pdd res = dfs(root);
        return res.first / 2 + res.second / 2;
    }
};

思路参考： 喂你脚下有坑