3203. 合并兩棵樹后的最小直徑
題目描述：
題如其意，給你兩棵樹，你可以從兩棵樹中各挑一個點出來，連一條邊，形成一個新的樹，問你最小直徑是多少
- 1 < = n , m < = 1 0 5 1 <= n, m <= 10^5 1<=n,m<=105
思路：
打力扣還是先觀察一下數據范圍的提示，發現給的兩棵樹的下標都是從0開始，所以正解可能不希望你把兩棵樹真正合并成一棵樹做
選的點肯定在直徑上，且是直徑的中點
設a，b分別是兩棵樹的直徑長度，則答案有三種情況：
- 第一棵樹的直徑很長，連邊后新樹的直徑仍未第一棵樹的直徑，答案是a
- 第二棵樹的直徑很長，連邊后新樹的直徑仍未第二棵樹的直徑，答案是b
- 新樹的直徑經過剛添加的邊，則答案是 ? a 2 ? + ? b 2 ? + 1 \lceil{\frac{a}{2}} \rceil+\lceil{\frac{b}{2}}\rceil + 1 ?2a??+?2b??+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;}
};
)
)
