3203.
好久没有遇到解这么顺的hard了
好感动qwq
顺顺写完
只有被原本树最长的小坑一下
很快修掉就过了
看起来跟大家写的一样
差在set好慢
然后max弄成阵列去比也好慢
class Solution {
public:
int minimumDiameterAfterMerge(vector<vector<int>>& edges1, vector<vector<int>>& edges2) {
// (dia1 + 1) / 2 + (dia2 + 1) / 2 + 1
int n = edges1.size() + 1, m = edges2.size() + 1;
vector<vector<int>> adj1(n), adj2(m);
for(auto& e: edges1){
adj1[e[0]].push_back(e[1]);
adj1[e[1]].push_back(e[0]);
}
for(auto& e: edges2){
adj2[e[0]].push_back(e[1]);
adj2[e[1]].push_back(e[0]);
}
int dia1 = 0, dia2 = 0;
unordered_set<int> seen1, seen2;
set_dia(0, adj1, dia1, seen1);
set_dia(0, adj2, dia2, seen2);
cout << dia1 << " " << dia2;
return max({dia1, dia2, ((dia1 + 1) / 2 + (dia2 + 1) / 2 + 1)});
}
int set_dia(int idx, vector<vector<int>>& adj, int& dia, unordered_set<int>& seen){
if(seen.count(idx)) return -1;
seen.insert(idx);
int mx1 = 0, mx2 = 0;
for(auto& i: adj[idx]){
int dep = set_dia(i, adj, dia, seen) + 1;
if(dep > mx1){
mx2 = mx1;
mx1 = dep;
}
else mx2 = max(mx2, dep);
dia = max({dia, mx1 + mx2, dep});
}
return mx1;
}
};

大师