LeetCode 136场双周赛 Q4. 标记所有节点需要的时间

这道题也是一道比较经典的树形dp模板题；太久没写了，赛时一眼就想到了，但是敲的时候摸索了半天，还是没敲出来；

首先看题目，需要求出 无向树上从每个节点为树根节点到其他所有节点中最长路径的值，然后每条边的距离其实就是，如果目的地是奇数距离为1，目的地是偶数距离为2
那么这个逻辑很简单，其实如果需要计算以A为树根到所有子节点的最长路径，其实就是求A下面的所有子树的最长路径 + 根节点到子节点的距离，那么其实就可以用递归的方式去做，将计算规模层层缩小，最后统计

那么简单来说就是树上向下搜索，加维护一下当前节点到所有子树中路径的前2大，为什么需要维护前二大，原因是题目需要计算每个节点的数据，那么需要前二大做优化
其实就是当统计完第一个根节点时，其实其他节点，只剩下它的父节点当时未统计，那么当我们需要拿到父节点的最大值时，不能把自己给重复统计进去，所以需要做判断，这里判断的逻辑是如果父节点最大的路径就是我自己的，那么就取第二大，否则取最大路径。，具体看代码吧

class Solution {
public:
    const static int maxn = 1e5 + 10;
    vector<int> v[maxn];
    int cnt[maxn][2];
    vector<int> timeTaken(vector<vector<int>>& edges) {
        for (int i = 0; i < maxn; ++ i) {
            v[i].clear();
        }

        for (int i = 0; i < edges.size(); ++ i) {
            int x = edges[i][0];
            int y = edges[i][1];

            v[x].push_back(y);
            v[y].push_back(x);
        }

        dfs(0, 0);
        dfs1(0, 0);

        vector<int> ans;
        ans.clear();
        for (int i = 0; i <= edges.size(); ++ i) {
            ans.push_back(cnt[i][0]);
        }
        return ans;
    }

    void dfs(int pos, int fa) {
        cnt[pos][0] = 0;
        cnt[pos][1] = 0;

        for (int i = 0; i < v[pos].size(); ++ i) {
            int son = v[pos][i];
            if (son == fa) {
                continue;
            }

            dfs(son, pos);
            int mx = cnt[son][0];
            if (son % 2 == 0) mx += 2;
            else mx += 1;
            if (mx >= cnt[pos][0]) {
                cnt[pos][1] = cnt[pos][0];
                cnt[pos][0] = mx;
            } else if (mx > cnt[pos][1]) {
                cnt[pos][1] = mx;
            }
        }
    }

    void dfs1(int pos, int fa) {
        for (int i = 0; i < v[pos].size(); ++ i) {
            int son = v[pos][i];
            if (son == fa) {
                continue;
            }

            int fa_mx = cnt[pos][0];
            int self_mx = cnt[son][0];
            if (son % 2 == 0) self_mx += 2;
            else self_mx ++;
            if (fa_mx == self_mx) {
                fa_mx = cnt[pos][1];
            }

            if (pos % 2 == 0) fa_mx += 2;
            else fa_mx ++;
            if (fa_mx >= cnt[son][0]) {
                cnt[son][1] = cnt[son][0];
                cnt[son][0] = fa_mx;
            } else if (fa_mx > cnt[son][1]) {
                cnt[son][1] = fa_mx;
            }

            dfs1(son, pos);
        }
    }
};