leetcode 404周赛 合并两棵树后最小直径「图论」「dp」

3203. 合并两棵树后的最小直径

题目描述：

题如其意，给你两棵树，你可以从两棵树中各挑一个点出来，连一条边，形成一个新的树，问你最小直径是多少

• $1<=n,m<=10^5$

思路：

打力扣还是先观察一下数据范围的提示，发现给的两棵树的下标都是从0开始，所以正解可能不希望你把两棵树真正合并成一棵树做

选的点肯定在直径上，且是直径的中点

设a，b分别是两棵树的直径长度，则答案有三种情况：

• 第一棵树的直径很长，连边后新树的直径仍未第一棵树的直径，答案是a
• 第二棵树的直径很长，连边后新树的直径仍未第二棵树的直径，答案是b
• 新树的直径经过刚添加的边，则答案是 $\lceil \frac{a}{2}\rceil +\lceil \frac{b}{2}\rceil +1$

class Solution {
public:
    int fuck(vector<vector<int>>& g){
        vector<vector<int>>G(g.size() + 1);
        for(auto x : g){
            G[x[0]].push_back(x[1]);
            G[x[1]].push_back(x[0]);
        }
        int ans = 0;
        auto dfs = [&](auto && dfs, int x, int fa) -> int{
            int maxn = 0;
            for(auto y : G[x]){
                if(y == fa)continue;
                int res = dfs(dfs, y, x) + 1;
                ans = max(ans, res + maxn);
                maxn = max(maxn, res);
            }
            return maxn;
        };
        dfs(dfs, 0, -1);
        return ans;
    }
    int minimumDiameterAfterMerge(vector<vector<int>>& G1, vector<vector<int>>& G2) {
        int a = fuck(G1), b = fuck(G2);
        int ans = max(max(a, b), (a+1) / 2 + (b + 1) / 2 + 1);
        return ans;
    }
};

原文地址：https://blog.csdn.net/weixin_51216553/article/details/140101487

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！