문제 링크

내 코드

2092ms, 373.95MB

class Solution {
public:
    int minimumDiameterAfterMerge(vector<vector<int>>& edges1, vector<vector<int>>& edges2) {
        int dia1 = calculateDiameter(edges1);
        int dia2 = calculateDiameter(edges2);

        int dia3 = ((dia1 + 1) >> 1) + ((dia2 + 1) >> 1) + 1;
        // 중간점끼리 잇기 + tree 연결하는 링크

        return max({dia1, dia2, dia3});
    }

private:
    const int VERTEX = 100'010;
    int calculateDiameter(vector<vector<int>>& edges) {
        vector<vector<int>> adj(VERTEX);

        for(vector<int>& edge : edges) {
            int a = edge[0], b = edge[1];
            adj[a].push_back(b);
            adj[b].push_back(a);
        }

        // 1. 임의의 정점(1번이라고 가정)에서 BFS 수행 -> 가장 먼 정점 A
        int A = bfs(0, adj).first;  // 1번에서 가장 멀리 있는 정점

        // 2. A에서 BFS 수행 -> 가장 먼 정점 B (A~B 사이 거리가 트리의 지름)
        return bfs(A, adj).second;
    }
    pair<int, int> bfs(int start, vector<vector<int>>& adj) {
        queue<pair<int, int>> q;
        vector visited(VERTEX + 1, false);
        
        q.push({start, 0}); // 거리이므로 현재 정점 포함 X(GPT가 맞음.)
        visited[start] = true;

        pair<int, int> farthest = {start, 0}; // 초기값

        while(!q.empty()) {
            auto [cur, dist] = q.front(); q.pop();

            // 현재까지 찾은 최대 거리보다 멀면 갱신
            if(dist > farthest.second) {
                farthest = {cur, dist};
            }

            // 인접 노드 순회
            for(auto &nxt : adj[cur]) {
                if(!visited[nxt]) {
                    visited[nxt] = true;
                    q.push({nxt, dist + 1});
                }
            }
        }
        // BFS를 다 돌고 나면, 시작점에서 가장 멀었던 정점과 그 거리를 반환
        return farthest;
    }
};

트리 지름

왜 트리의 지름을 DFS 2번(또는 BFS 2번)으로 구할 수 있을까?
트리에서 지름(Diameter)이란 트리를 구성하는 모든 경로 중 가장 긴 경로의 길이를 말합니다. 트리의 한 정점에서 다른 정점까지 이동하는 경로는 유일하게 정해지기 때문에, 지름을 구하려면 “가장 긴 경로가 되는 두 정점”을 찾으면 됩니다.

트리 지름을 구하는 고전적인 방법은 다음과 같습니다:

1. 트리에서 임의의 정점 $u$를 잡고, $u$로부터 가장 먼(거리 최댓값) 정점 $v$를 찾는다.
2. 찾은 정점 $v$로부터 다시 가장 먼 정점 $w$를 찾는다.
3. 이때 $v$와 $w$ 사이의 거리가 트리의 지름이다.

여기서 1~2번 과정에서 “가장 먼 정점 찾기”는 DFS(또는 BFS)를 통해 간단히 구할 수 있습니다.

---

왜 이렇게 하면 지름을 구할 수 있을까? (개략적인 증명)

• 임의의 정점 $u$를 잡고 가장 먼 정점 $v$를 찾으면, $v$는 지름을 이루는 경로상의 한 끝점이다.
  트리의 지름 경로를 $P$라 하자. $u$에서 가장 먼 정점이 $v$인데, 만약 지름 경로가 $v$를 끝점으로 삼지 않는다고 가정하면, $v$보다 더 먼 정점을 통해 더 긴 경로를 만들 수 있게 됩니다. 이는 $v$가 “가장 먼 정점”이라는 정의에 모순이므로 $v$는 지름 경로 끝점이 됩니다.

• 다시 한 번, $v$로부터 가장 먼 정점 $w$를 찾으면, $v$와 $w$ 간의 경로가 지름이 된다.
  이미 $v$가 지름을 이루는 경로 중 하나의 끝점이라는 것은 위에서 보았습니다. 이제 $v$에서 가장 먼 정점 $w$로 가는 경로의 길이는 곧 트리 내에서 가능한 경로 중 가장 긴 길이가 됩니다.

이 과정을 DFS나 BFS로 구현하면, 두 번의 탐색으로 트리의 지름을 구할 수 있습니다.

---

C++ 코드 예시 (DFS를 이용한 트리의 지름 구하기)

다음 코드는

• 정점 개수 $N$,
• 간선 정보(총 $N-1$개)를 입력받아 인접 리스트를 구성한 뒤,
• “DFS 2번” 방식을 이용해 지름을 구합니다.

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100000;
vector<int> adj[MAXN + 1];  // 인접 리스트(1-based index 가정)

int N;

// (현재 정점, 부모 정점, 현재까지 거리, 가장 멀리 떨어진 정점, 최장 거리)
void dfs(int node, int parent, int dist, int &farthestNode, int &maxDist) {
    if (dist > maxDist) {
        maxDist = dist;
        farthestNode = node;
    }
    for (auto &next : adj[node]) {
        if (next == parent) continue;
        dfs(next, node, dist + 1, farthestNode, maxDist);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;
    for(int i = 0; i < N-1; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // 1. 임의의 정점(여기서는 1번이라 가정)에서 가장 먼 정점 A 찾기
    int A = 1, maxDist = -1;
    dfs(1, -1, 0, A, maxDist);

    // 2. A에서 가장 먼 정점 B 찾기
    int B = A;
    maxDist = -1;
    dfs(A, -1, 0, B, maxDist);

    // maxDist가 A와 B 사이의 거리 = 트리의 지름
    cout << maxDist << "\n";

    return 0;
}

코드 동작 방식

1. 인접 리스트 구성

   • 간선 정보를 입력받아 adj[u], adj[v] 에 서로를 추가합니다.

2. 첫 번째 DFS

   • 임의의 정점(1번)에서 dfs(1, -1, 0, A, maxDist) 실행.
   • 1번 정점에서 가장 멀리 떨어진 정점 A를 찾습니다.

3. 두 번째 DFS

   • 찾은 정점 A에서 dfs(A, -1, 0, B, maxDist) 실행.
   • 이번엔 A에서 가장 멀리 떨어진 정점 B를 찾고, 그 거리 maxDist가 곧 지름이 됩니다.

이처럼 트리에서 두 번의 DFS(또는 BFS)를 사용하여 간단하게 지름을 구할 수 있습니다.

---

핵심 정리

• 트리에서 임의의 노드에서 가장 먼 노드를 구하면, 그 노드는 지름을 이루는 경로의 한 끝점이 된다.
• 그 끝점에서 다시 가장 먼 노드를 구하면 두 끝점 간 거리가 지름이 된다.

위 원리를 이용하면, 어떤 노드를 시작점으로 잡아도 항상 정확한 지름을 구할 수 있게 됩니다.

BFS 코드?!

아래 코드는 BFS를 두 번 사용하여 트리의 지름을 구하는 간단한 예시입니다.

---

트리 지름을 구하는 BFS 알고리즘 개요

1. 임의의 정점 $u$에서 BFS를 수행하여, 가장 먼 정점(거리 최댓값)인 $v$를 찾는다.
2. 정점 $v$에서 다시 BFS를 수행하여, 가장 먼 정점 $w$를 찾는다.
3. $v$와 $w$ 사이의 거리가 곧 트리의 지름이다.

---

C++ 코드 예시

#include <bits/stdc++.h>
using namespace std;

static const int MAXN = 100000;  // 문제에 맞게 조정
vector<int> adj[MAXN + 1];

int N;

pair<int, int> bfs(int start) {
    // pair<int, int> = (가장 먼 정점, 거리)
    // 큐에는 (정점, 거리)를 저장
    queue<pair<int, int>> q;
    vector<bool> visited(N+1, false);
    
    q.push({start, 0});
    visited[start] = true;

    pair<int, int> farthest = {start, 0}; // 초기값

    while(!q.empty()) {
        auto [cur, dist] = q.front();
        q.pop();

        // 현재까지 찾은 최대 거리보다 멀면 갱신
        if(dist > farthest.second) {
            farthest = {cur, dist};
        }

        // 인접 노드 순회
        for(auto &nxt : adj[cur]) {
            if(!visited[nxt]) {
                visited[nxt] = true;
                q.push({nxt, dist + 1});
            }
        }
    }
    // BFS를 다 돌고 나면, 시작점에서 가장 멀었던 정점과 그 거리를 반환
    return farthest;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;
    for(int i = 0; i < N-1; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // 1. 임의의 정점(1번이라고 가정)에서 BFS 수행 -> 가장 먼 정점 A
    pair<int, int> tmp = bfs(1);
    int A = tmp.first;  // 1번에서 가장 멀리 있는 정점

    // 2. A에서 BFS 수행 -> 가장 먼 정점 B (A~B 사이 거리가 트리의 지름)
    pair<int, int> result = bfs(A);
    int B = result.first;     // A에서 가장 먼 정점
    int diameter = result.second;  // 트리의 지름

    cout << diameter << "\n";
    return 0;
}

코드 설명

1. 인접 리스트 구성

   • $N-1$개의 간선을 받아서 adj[u].push_back(v) / adj[v].push_back(u) 로 그래프를 구성합니다.

2. BFS 함수 (bfs)

   • 시작 정점 start로부터 BFS를 수행하여
     • 방문 배열 visited를 사용해 중복 방문을 방지합니다.
     • 큐에는 (현재 정점, 거리)를 저장합니다.
   • BFS 도중 “가장 멀리 떨어진 정점”을 farthest로 갱신해나가면서 최종적으로 (정점 번호, 거리)를 반환합니다.

3. 지름 계산

   • 임의의 정점(예: 1번)에서 BFS를 실행하여 가장 먼 정점 A를 찾습니다.
   • 정점 A를 시작점으로 다시 BFS를 실행하여 가장 먼 정점 B와 그 거리를 찾습니다.
   • 이 거리(diameter)가 트리의 지름이 됩니다.

---

핵심 포인트

• DFS 방식이든 BFS 방식이든, “두 번의 탐색”으로 트리의 지름을 구할 수 있습니다.
• 트리에서 임의의 정점에서 시작하면, 그 정점에서 가장 멀리 있는 정점은 항상 지름을 이루는 경로의 한 쪽 끝점이 된다는 것이 핵심 이론적 근거입니다.
• 이후 그 끝점에서 다시 탐색을 하면, 전체 트리에서 가장 먼 반대편 끝점을 발견할 수 있고, 그 거리 값이 바로 트리의 지름이 됩니다.

이렇게 BFS 두 번으로도 트리 지름을 구할 수 있습니다.

Solution

Approach 1: Farthest of Farthest (BFS)

• 448ms, 325.52MB
• Complexity
  • Let $n$ be the number of nodes in the first tree and $m$ the number of nodes in the second tree.
  • Time Complexity: $O(n + m)$
  • Space Complexity: $O(n + m)$

class Solution {
public:
    int minimumDiameterAfterMerge(vector<vector<int>>& edges1,
                                  vector<vector<int>>& edges2) {
        // Calculate the number of nodes for each tree
        int n = edges1.size() + 1;
        int m = edges2.size() + 1;

        // Build adjacency lists for both trees
        vector<vector<int>> adjList1 = buildAdjList(n, edges1);
        vector<vector<int>> adjList2 = buildAdjList(m, edges2);

        // Calculate the diameters of both trees
        int diameter1 = findDiameter(n, adjList1);
        int diameter2 = findDiameter(m, adjList2);

        // Calculate the longest path that spans across both trees
        int combinedDiameter =
            ceil(diameter1 / 2.0) + ceil(diameter2 / 2.0) + 1;

        // Return the maximum of the three possibilities
        return max({diameter1, diameter2, combinedDiameter});
    }

private:
    vector<vector<int>> buildAdjList(int size, vector<vector<int>>& edges) {
        vector<vector<int>> adjList(size);
        for (auto edge : edges) {
            adjList[edge[0]].push_back(edge[1]);
            adjList[edge[1]].push_back(edge[0]);
        }
        return adjList;
    }

    // Function to find the diameter of a tree using two BFS calls
    int findDiameter(int n, vector<vector<int>>& adjList) {
        // First BFS to find the farthest node from any arbitrary node (e.g., 0)
        auto [farthestNode, _] = findFarthestNode(n, adjList, 0);

        // Second BFS from the farthest node to determine the diameter
        auto [_, diameter] = findFarthestNode(n, adjList, farthestNode);
        return diameter;
    }

    // BFS helper function to find the farthest node and its distance from the
    // source
    pair<int, int> findFarthestNode(int n, vector<vector<int>>& adjList,
                                    int sourceNode) {
        queue<int> nodesQueue;
        vector<bool> visited(n, false);
        // Push source node into the queue
        nodesQueue.push(sourceNode);
        visited[sourceNode] = true;

        int maximumDistance = 0, farthestNode = sourceNode;

        // Explore neighbors
        while (!nodesQueue.empty()) {
            int size = nodesQueue.size();
            for (int i = 0; i < size; ++i) {
                int currentNode = nodesQueue.front();
                nodesQueue.pop();
                // Update farthest node
                // The farthest node is the last one that was popped out of the
                // queue.
                farthestNode = currentNode;

                for (int neighbor : adjList[currentNode]) {
                    // Explore neighbors
                    if (!visited[neighbor]) {
                        visited[neighbor] = true;
                        nodesQueue.push(neighbor);
                    }
                }
            }
            if (!nodesQueue.empty()) maximumDistance++;
        }
        return {farthestNode, maximumDistance};
    }
};

GPT

아래 코드는 두 개의 트리가 주어졌을 때, 각각의 트리와 이 둘을 “하나의 간선으로 연결했을 때의 (사실상) 합쳐진 트리”에서 가능한 최소 직경(지름)을 구하여, 그 중 최대값(세 후보 중 최댓값)을 반환하는 로직으로 보입니다.

---

문제 맥락 (유추)

1. 입력:
   • 두 개의 트리(edges1, edges2).
   • 각각 노드 수는 n = edges1.size() + 1, m = edges2.size() + 1으로 계산 (트리는 간선 수 = 노드 수 - 1).
2. 출력:
   • $\max(\,\text{diameter}(T_1),\ \text{diameter}(T_2),\ \text{combinedDiameter}\,)$
   • 여기서 $\text{combinedDiameter}$는 두 트리를 새 간선 하나로 연결했을 때의 직경(단, 최소화를 위해 어떤 식으로 두 트리를 연결하느냐를 최적적으로 선택했다고 가정).

왜 “직경” 중 최댓값을 반환하나?

코드에서는 return max({diameter1, diameter2, combinedDiameter});로 결과를 반환합니다.

• $\text{diameter1}$, $\text{diameter2}$는 각각 트리1, 트리2의 직경.
• $\text{combinedDiameter}$는 두 트리를 하나의 간선으로 연결했을 때 가능한 직경 중 최소 값을 나타낸다고 해석할 수 있습니다(“minimumDiameterAfterMerge”라는 함수명).
• 최종적으로, $\max(\text{diameter1}, \text{diameter2}, \text{combinedDiameter})$를 구하고 있습니다.

이는 “합쳐진 트리의 최소 직경”을 구해서, 그 값과 기존 각 트리의 직경과의 최댓값을 취한다는 로직입니다. 문제 의도에 따라 “트리를 합쳤을 때 최소 직경이 얼마이고, 그와 기존 직경들을 비교해 그 중 최댓값을 반환”하는 시나리오로 보입니다.

---

코드 단계별 해설

int minimumDiameterAfterMerge(vector<vector<int>>& edges1,
                              vector<vector<int>>& edges2) {
    // 1. 각각의 트리에 대한 노드 수
    int n = edges1.size() + 1;
    int m = edges2.size() + 1;

    // 2. 인접 리스트 생성
    vector<vector<int>> adjList1 = buildAdjList(n, edges1);
    vector<vector<int>> adjList2 = buildAdjList(m, edges2);

    // 3. 각각의 직경 계산
    int diameter1 = findDiameter(n, adjList1);
    int diameter2 = findDiameter(m, adjList2);

    // 4. 두 트리를 연결했을 때의 "최소화된" 직경 추정치
    //    ceil(diameter1 / 2.0) + ceil(diameter2 / 2.0) + 1
    int combinedDiameter = ceil(diameter1 / 2.0) + ceil(diameter2 / 2.0) + 1;

    // 5. 세 후보 중 최댓값을 반환
    return max({diameter1, diameter2, combinedDiameter});
}

1. 노드 수:
   • 트리1은 간선이 edges1.size()개이므로, 노드 수 n = edges1.size() + 1.
   • 트리2는 m = edges2.size() + 1.
2. 인접 리스트 구성:

   vector<vector<int>> buildAdjList(int size, vector<vector<int>>& edges) {
       vector<vector<int>> adjList(size);
       for (auto edge : edges) {
           adjList[edge[0]].push_back(edge[1]);
           adjList[edge[1]].push_back(edge[0]);
       }
       return adjList;
   }

3. findDiameter 로 각 트리 직경 찾기:

   int findDiameter(int n, vector<vector<int>>& adjList) {
       // 임의 노드(여기서는 0)에서 가장 먼 노드(A)를 찾고,
       auto [farthestNode, _] = findFarthestNode(n, adjList, 0);
       // 그 노드(A)로부터 가장 먼 노드까지의 거리 = 직경
       auto [_, diameter] = findFarthestNode(n, adjList, farthestNode);
       return diameter;
   }

   • 두 번의 BFS를 이용한 표준적인 트리 지름(diameter) 계산 방식.
     1. 임의 노드(0)에서 가장 먼 노드를 찾음 → 그 노드를 farthestNode라 하자.
     2. farthestNode에서 다시 BFS를 돌려 가장 먼 거리 = diameter.
4. 두 트리 합쳤을 때 직경을 최소화하는 방안
   • 알고리즘 아이디어: 트리1의 지름 경로 중간(약 절반 지점)과 트리2의 지름 경로 중간(약 절반 지점)을 연결하면, 두 트리가 붙었을 때의 전체 경로 길이가 $\lceil \frac{diameter1}{2} \rceil + \lceil \frac{diameter2}{2} \rceil + 1$ 정도가 된다는 것이 널리 알려진 그리디 방식.
   • 즉, 지름 경로의 양끝을 연결하는 대신 “지름의 가운데”끼리 연결해야 합쳤을 때의 직경이 최소가 됩니다.
   • 그래서 combinedDiameter = $\lceil \frac{d_1}{2} \rceil + \lceil \frac{d_2}{2} \rceil + 1$.
5. 최종 반환: max(diameter1, diameter2, combinedDiameter).
   • 결과적으로, “트리1만 봤을 때 지름”, “트리2만 봤을 때 지름”, 그리고 “두 트리를 붙여 만든 트리의 (가능한) 최소 지름” 세 값 중 최댓값을 반환합니다.

---

보조 함수: 지름 찾기와 BFS

$\text{findFarthestNode}$

pair<int, int> findFarthestNode(int n, vector<vector<int>>& adjList, int sourceNode) {
    queue<int> nodesQueue;
    vector<bool> visited(n, false);

    nodesQueue.push(sourceNode);
    visited[sourceNode] = true;

    int maximumDistance = 0, farthestNode = sourceNode;

    // 레벨 단위 BFS
    while (!nodesQueue.empty()) {
        int size = nodesQueue.size();
        for (int i = 0; i < size; i++) {
            int currentNode = nodesQueue.front();
            nodesQueue.pop();
            // 이 BFS의 "마지막으로 꺼낸 노드"가 farthestNode
            farthestNode = currentNode;

            for (int neighbor : adjList[currentNode]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    nodesQueue.push(neighbor);
                }
            }
        }
        // 한 레벨 끝날 때 distance +1
        if (!nodesQueue.empty()) maximumDistance++;
    }
    return {farthestNode, maximumDistance};
}

• 이 BFS는 “트리에서 sourceNode로부터의 최장거리” 를 구하는 표준 로직입니다.
• 레벨 개념으로, 한 번의 while 루프(한 레벨) 끝날 때 maximumDistance++.
• farthestNode는 “현재 레벨에서 마지막으로 pop된 노드”가 됩니다.
• 최종 return {farthestNode, maximumDistance};로, 가장 먼 노드와 그 거리(=레벨 수)를 전달.

$\text{findDiameter}$

int findDiameter(int n, vector<vector<int>>& adjList) {
    // 1) source=0 에서 제일 먼 노드 = A
    auto [farthestNode, _] = findFarthestNode(n, adjList, 0);
    // 2) A 에서 제일 먼 노드까지 거리 = diameter
    auto [_, diameter] = findFarthestNode(n, adjList, farthestNode);
    return diameter;
}

---

핵심 포인트

1. 트리 직경(diameter) 계산: 두 번의 BFS/DFS 사용. (가장 흔한 접근)
2. 두 트리를 “최소 직경”으로 연결: 각 트리의 지름 경로의 중앙을 연결하면,
   • $\text{새 트리의 직경} \approx \lceil \frac{d_1}{2} \rceil + \lceil \frac{d_2}{2} \rceil + 1$
3. 최종: 세 값(트리1 지름, 트리2 지름, 합쳐진 트리의 최소 지름) 중 최댓값 반환.

---

예시 간단 시뮬레이션

• 트리1 (5 nodes): 지름 = 3
• 트리2 (4 nodes): 지름 = 2
  • $\lceil \frac{3}{2} \rceil = 2$, $\lceil \frac{2}{2} \rceil = 1$.
  • combinedDiameter = 2 + 1 + 1 = 4.
• $\max(3, 2, 4) = 4$.

---

결론

• 두 트리가 주어졌을 때, 각 트리의 직경과, 두 트리를 연결해 하나의 트리로 만들 때 얻을 수 있는 가장 작은 직경(= $\lceil d_1/2 \rceil + \lceil d_2/2 \rceil + 1$)을 구하고, 이 세 값의 최댓값을 반환합니다.
• 코드는 이 로직을 간단한 BFS/인접 리스트 방식으로 구현한 예시입니다.
• “$\frac{d}{2}$ 위치”로 연결한다는 아이디어 덕분에 합쳐진 트리의 직경을 비교적 간단히 추정할 수 있습니다.

왜 올림을 해야 하는가?

트리 두 개를 간선 하나로 연결했을 때 “그 합쳐진 트리의 직경(diameter)을 최소로 만들려면” 주로 알려진 방법이 각 트리의 지름 경로(diameter path) 가운데(중심부)끼리 연결하는 것입니다.
이때 새로 합쳐진 트리의 직경이
$\Bigl\lceil \tfrac{d_1}{2} \Bigr\rceil + \Bigl\lceil \tfrac{d_2}{2} \Bigr\rceil + 1$
(또는 상황에 따라 $\lfloor\,\rfloor$를 쓸 수도 있음)
형태로 계산되는 이유를 단계별로 살펴보겠습니다.

---

1. 트리의 지름(diameter)과 ‘가운데’(중심부) 개념

• 어떤 트리의 지름 $d$은 “가장 먼 두 노드 사이의 거리”입니다.
• 이 지름 경로의 길이가 짝수라면, 한가운데 노드가 정확히 1개(중심 노드)가 존재합니다. 예) 지름이 4라면 경로가 5개 노드이고, 그 가운데 노드는 3번째 노드.
• 지름이 홀수라면, 경로의 중앙이 간선으로 떨어집니다(중심 노드가 2개). 예) 지름이 3이라면 경로가 4개 노드고, 가운데가 노드와 노드 사이.

중심부에서 가장 먼 거리

• 지름이 짝수 $d$이면, “가운데 노드에서 양끝 노드까지의 거리”가 $d/2$.
• 지름이 홀수 $d$이면, 가운데가 노드 사이(간선) 형태라 실제 중앙까지의 거리는 $d/2$이지만, 노드로만 이동해야 하므로 보통 $\lfloor d/2 \rfloor$ 혹은 $\lceil d/2 \rceil$를 고려해야 합니다.
  • 예: $d=3$이면 경로가 4노드짜리. 엄밀히 말하면 중간이 1.5 간선 지점이지만, 노드는 정수 위치에만 존재하므로 실제 “가장 가까운 중간 노드”로부터 끝까지의 거리는 1 또는 2가 됩니다.
  • 어떤 상황에서는 $\lfloor d/2 \rfloor$가, 또 어떤 상황에서는 $\lceil d/2 \rceil$가 “중심 노드(또는 가장 중앙에 있는 그 둘 중 하나)에서 끝까지의 최대 거리”로 잡힙니다.

---

2. 두 트리의 지름 경로 ‘중앙’끼리 연결하면 직경이 최소가 되는 이유

(1) 왜 양끝이 아니라 ‘중간’을 연결하는가?

• 트리1의 지름 경로 양끝(A, B) 중 어느 한쪽 끝, 그리고 트리2의 지름 경로 양끝(C, D) 중 어느 한쪽 끝을 연결해버리면,
  • 새로 만들어진 트리에서 A–(경로)–B 와 C–(경로)–D도 볼 수 있는데, 합쳐진 전체 경로가 길어질 수 있습니다.
• 반면 “지름 경로의 한복판(중심부)”끼리를 연결하면, 각 트리 내부에서 최악의 거리(지름의 절반 정도) + 연결 간선(1) + 다른 트리 내부 최악의 거리 정도만큼이 최대가 되므로, 전체 직경을 가장 짧게 만들 수 있습니다.

(2) 실제 거리 계산: $\lceil \tfrac{d_1}{2} \rceil + \lceil \tfrac{d_2}{2} \rceil + 1$

• 트리1 지름 = $d_1$. 중심부(또는 중심 노드)에 서서 트리1 내부의 최악(가장 먼) 노드까지 가는 거리는 대략 $\lceil d_1/2 \rceil$.
• 트리2 지름 = $d_2$. 중심부 기준 트리2 내부 최악 노드까지도 $\lceil d_2/2 \rceil$.
• 두 중심부끼리 연결하는 데 간선이 1개.
• 따라서 “합쳐진 트리에서 가장 멀리 떨어진 노드끼리” 이동 거리는 대략
  $\Bigl\lceil \tfrac{d_1}{2} \Bigr\rceil \;+\; 1 \;+\; \Bigl\lceil \tfrac{d_2}{2} \Bigr\rceil.$
  이 값이 새 트리의 최대 거리(즉 직경) 후보가 됩니다.

$\lceil\cdot\rceil$ vs $\lfloor\cdot\rfloor$

• 지름이 짝수라면, 실제 중앙 노드가 존재하므로 $\tfrac{d}{2}$가 정수이며, $\lfloor d/2\rfloor = \lceil d/2\rceil$.
• 지름이 홀수인 경우 중간이 간선이라, 중앙에서 끝까지 “1.5간선” 같은 분수 상황이 생깁니다.
  • 어떤 문제 세팅에서는 $\lfloor \tfrac{d}{2}\rfloor$를 쓰기도, 또 다른 데서는 $\lceil \tfrac{d}{2}\rceil$를 쓰기도 합니다.
  • 본 코드에서는 $\lceil$를 사용했는데, “중심에 가장 가까운 노드”로부터 끝 노드까지의 최대 거리가 $\lceil d/2\rceil$이 되기 때문입니다(트리 경로가 정수이므로, 실제 ‘완벽 중앙’은 간선 한가운데이므로 한쪽 노드로 치우치면 최대 거리가 $\lceil\cdot\rceil$가 될 수 있음).

---

3. “버림($\lfloor$) 또는 올림($\lceil$)”을 왜 하는가?

• 트리는 간선이 불연속(정수) 단위이므로, 지름이 홀수일 때 “정확히 중앙”이 노드가 아닌 간선 사이에 위치하게 됩니다.
• 어떤 노드를 “중심”으로 잡더라도,
  • $\lfloor d/2\rfloor$ 또는 $\lceil d/2\rceil$만큼 멀리 떨어진 노드가 생길 수 있습니다.
• 그래서 “최악”의 경우(가장 먼 거리)를 보장하려면, 보수적으로 $\lceil\cdot\rceil$를 쓰는 편이 안전할 때가 많습니다.
  • 예를 들어 지름이 3인 트리는 경로가 4개의 노드로 구성됩니다. 중앙이 1.5간선 지점이니,
    • 한쪽 노드를 중심으로 잡으면 “끝까지 거리”가 2가 될 수도 있습니다($\lceil 3/2\rceil=2$).
    • 만약 $\lfloor\cdot\rfloor=1$이라고 단순 계산했는데 실제로는 2가 걸리는 노드가 있으면, 계산이 틀립니다.
• 즉, 가장 멀리 갈 수 있는 노드를 감안하면 올림($\lceil\cdot\rceil$)이 필요하다는 것이죠.

정리하면, 홀수 지름에서 중심 “노드”로 선택했을 때는 어느 쪽이든 최대 거리가 $\lceil d/2\rceil$가 될 수 있으므로,
$\text{(트리1 내부 최악 거리)} + 1 + \text{(트리2 내부 최악 거리)} \;=\; \Bigl\lceil \tfrac{d_1}{2} \Bigr\rceil + \Bigl\lceil \tfrac{d_2}{2} \Bigr\rceil + 1$ 로 계산해야 안전하게 “합쳐진 트리의 최대 거리(직경)”를 예측할 수 있습니다.

---

결론

1. 두 트리 지름 경로의 ‘중심부’(중앙)끼리 연결 → 합쳐진 트리의 직경이 최소가 된다.
2. 지름이 홀수일 때 중앙이 간선 사이이므로, 어느 한쪽 노드를 중앙처럼 잡았을 때 끝 노드까지의 최대 거리는 $\lceil d/2\rceil$가 될 수 있다.
   • 이 때문에 $\lfloor\cdot\rfloor$보다 $\lceil\cdot\rceil$를 사용해 “최악 거리”를 커버해야 한다.
3. 최종적으로,
   $\bigl\lceil \tfrac{d_1}{2} \bigr\rceil \;+\; 1 \;+\; \bigl\lceil \tfrac{d_2}{2} \bigr\rceil$ 이 두 트리를 하나의 간선으로 연결했을 때 얻을 수 있는 최소 직경(가장 짧은 최댓값)으로 알려져 있습니다.

• “버림($\lfloor$) 대신 왜 올림($\lceil$)을 쓰나?” → 홀수 지름에서의 실제 노드 중심이 편향되어 “최악 거리가 생각보다 1 많아질 수 있기 때문”입니다.
• “짝수 지름”인 경우는 $\lfloor$와 $\lceil$ 모두 $d/2$로 동일하므로 문제가 되지 않습니다.

Approach 2: Depth First Search

• 282ms, 299.241MB
• Complexity
  • Let $n$ be the number of nodes in the first tree and $m$ the number of nodes in the second tree.
  • Time Complexity: $O(n + m)$
  • Space Complexity: $O(n + m)$

class Solution {
public:
    int minimumDiameterAfterMerge(vector<vector<int>>& edges1,
                                  vector<vector<int>>& edges2) {
        // Calculate the number of nodes for each tree (number of edges + 1)
        int n = edges1.size() + 1;
        int m = edges2.size() + 1;

        // Build adjacency lists for both trees
        vector<vector<int>> adjList1 = buildAdjList(n, edges1);
        vector<vector<int>> adjList2 = buildAdjList(m, edges2);

        int diameter1 =
            findDiameter(adjList1, 0, -1).first;  // Start DFS for Tree 1
        int diameter2 =
            findDiameter(adjList2, 0, -1).first;  // Start DFS for Tree 2

        // Calculate the diameter of the combined tree
        // This accounts for the longest path spanning both trees
        int combinedDiameter =
            ceil(diameter1 / 2.0) + ceil(diameter2 / 2.0) + 1;

        // Return the maximum diameter among the two trees and the combined tree
        return max({diameter1, diameter2, combinedDiameter});
    }

private:
    // Helper function to build an adjacency list from an edge list
    vector<vector<int>> buildAdjList(int size, vector<vector<int>>& edges) {
        vector<vector<int>> adjList(size);
        for (auto& edge : edges) {
            adjList[edge[0]].push_back(edge[1]);
            adjList[edge[1]].push_back(edge[0]);
        }
        return adjList;
    };

    // Helper function to find the diameter of a tree
    // Returns the diameter and the depth of the node's subtree
    pair<int, int> findDiameter(vector<vector<int>>& adjList, int node,
                                int parent) {
        int maxDepth1 = 0,
            maxDepth2 =
                0;  // Tracks the two largest depths from the current node
        int diameter = 0;  // Tracks the diameter of the subtree

        for (int neighbor :
             adjList[node]) {  // Iterate through neighbors of the current node
            if (neighbor == parent)
                continue;  // Skip the parent to avoid cycles

            // Recursively calculate the diameter and depth of the neighbor's
            // subtree
            auto [childDiameter, depth] = findDiameter(adjList, neighbor, node);

            // Update the maximum diameter of the subtree
            diameter = max(diameter, childDiameter);

            depth++;  // Increment the depth to include the edge to this
                      // neighbor
            // Update the two largest depths from the current node
            if (depth > maxDepth1) {
                maxDepth2 = maxDepth1;
                maxDepth1 = depth;
            } else if (depth > maxDepth2) {
                maxDepth2 = depth;
            }
        }

        // Update the diameter to include the path through the current node
        diameter = max(diameter, maxDepth1 + maxDepth2);

        return {diameter, maxDepth1};
    }
};

GPT

아래 코드는 두 개의 트리(Tree) 를 입력받아,

1. 각각의 트리 자체의 지름(직경)을 구하고,
2. 두 트리를 간선 하나로 연결했을 때(“합쳐진 트리”에서) 가능한 최소 직경을 구한 뒤,
   이 셋(트리1 지름, 트리2 지름, 합쳐진 트리 최소 지름) 중 최댓값을 결과로 반환합니다.

---

1. 전체 흐름

int minimumDiameterAfterMerge(vector<vector<int>>& edges1,
                              vector<vector<int>>& edges2) {
    // 1) 트리1, 트리2 노드 수
    int n = edges1.size() + 1;
    int m = edges2.size() + 1;

    // 2) 인접 리스트 생성
    vector<vector<int>> adjList1 = buildAdjList(n, edges1);
    vector<vector<int>> adjList2 = buildAdjList(m, edges2);

    // 3) 트리1, 트리2 각각 지름(diameter) 계산
    //    findDiameter()는 (해당 트리의 지름, 해당 노드의 서브트리 최대 깊이)를 반환
    int diameter1 = findDiameter(adjList1, 0, -1).first;
    int diameter2 = findDiameter(adjList2, 0, -1).first;

    // 4) 두 트리를 합쳤을 때의 최소 직경 계산
    //    지름 d1, d2 -> 합쳐진 트리의 최소 직경 = ceil(d1/2) + ceil(d2/2) + 1
    int combinedDiameter = ceil(diameter1 / 2.0) + ceil(diameter2 / 2.0) + 1;

    // 5) 세 값 중 최댓값을 반환
    return max({diameter1, diameter2, combinedDiameter});
}

(A) 두 트리를 합쳐서 얻을 수 있는 최소 직경

• 지름이 $d_1$인 트리와 $d_2$인 트리를 각각 갖고 있을 때,
  • 각 트리의 “지름 경로” 중 가운데(약 절반 지점)끼리 연결하면, 합쳐진 트리의 직경이 보통
    $\bigl\lceil d_1/2 \bigr\rceil \;+\; \bigl\lceil d_2/2 \bigr\rceil \;+\; 1$ 로 최소화되는 것이 알려져 있습니다.
  • 코드에서는 이를 combinedDiameter로 계산하고, 그와 기존 지름들($d_1, d_2$) 중 최댓값을 반환합니다.

---

2. 인접 리스트 구성 buildAdjList()

vector<vector<int>> buildAdjList(int size, vector<vector<int>>& edges) {
    vector<vector<int>> adjList(size);
    for (auto& edge : edges) {
        adjList[edge[0]].push_back(edge[1]);
        adjList[edge[1]].push_back(edge[0]);
    }
    return adjList;
}

• 주어진 edges 목록을 이용하여, 각 노드별로 연결된 이웃 노드를 adjList[node]에 기록합니다.
• (노드 번호가 0부터 시작한다고 가정)

---

3. 지름(diameter) 계산: findDiameter()

이 코드는 DFS 1회만으로 “(서브)트리의 최대 직경”과 “현재 노드에서의 최대 깊이”를 동시에 구하는 Post-order DFS 방식입니다.

pair<int,int> findDiameter(vector<vector<int>>& adjList, int node, int parent) {
    // maxDepth1, maxDepth2: 현재 노드에서 가장 깊은 두 경로의 길이
    // diameter: 서브트리 전체에서 발견한 최대 지름
    int maxDepth1 = 0, maxDepth2 = 0;  
    int diameter = 0;

    for (int neighbor : adjList[node]) {
        if (neighbor == parent) continue;  // 부모(이미 방문) 무시

        // 자식(이웃) 방향으로 DFS
        auto [childDiameter, depth] = findDiameter(adjList, neighbor, node);

        // 자식 서브트리의 지름이 더 크면 갱신
        diameter = max(diameter, childDiameter);

        // 자식까지의 depth + 1 → 현재 node 기준 depth
        depth++;
        // 가장 깊은 두 경로 갱신
        if (depth > maxDepth1) {
            maxDepth2 = maxDepth1;
            maxDepth1 = depth;
        } else if (depth > maxDepth2) {
            maxDepth2 = depth;
        }
    }

    // "현재 노드"를 거치는 경로( maxDepth1 + maxDepth2 )가 더 클 수 있음
    diameter = max(diameter, maxDepth1 + maxDepth2);

    // (결과 지름, 현재 노드에서 뻗어나가는 최대 깊이)
    return {diameter, maxDepth1};
}

동작 원리

1. DFS를 통해 neighbor(자식) 서브트리의 (지름, 최대깊이)를 얻는다.
2. childDiameter와 지금까지의 diameter 중 큰 값을 취해, 서브트리의 지름으로 갱신.
3. depth + 1을 계산하여 “현재 노드에서 그 자식 쪽으로 뻗어나가는 깊이”를 구한다.
   • 이 값을 기준으로, 현재 노드에서 가장 깊은 경로 2개(maxDepth1, maxDepth2)를 추적한다.
4. “현재 노드”에서 양쪽으로 가장 깊은 두 경로를 더하면, 이 노드를 경유하는 경로의 길이가 됨.
   • 이를 maxDepth1 + maxDepth2로 계산, 만약 이것이 diameter보다 크다면 갱신.
5. 최종적으로 (diameter, maxDepth1)을 반환.
   • diameter: 현재 노드를 루트로 하는 서브트리에서의 최대 지름
   • maxDepth1: 현재 노드에서 뻗어나가는 가장 깊은 경로 길이 (부모 쪽에서 사용할 수 있도록)

이 기법을 사용하면, DFS 한 번으로 해당 트리(또는 서브트리)의 지름을 알아낼 수 있습니다. (보다 전통적인 2번 BFS/DFS 방식도 있지만, 여기서는 “가장 깊은 두 경로” 조합으로 동시에 해결)

---

4. 최종 결론

• 트리1의 지름 = diameter1, 트리2의 지름 = diameter2
• 두 트리를 한 간선으로 연결했을 때 직경을 최소화하려면, 각 트리 지름 경로의 중앙을 연결 → 결과 직경 = $\lceil d_1/2 \rceil + \lceil d_2/2 \rceil + 1$
• 세 값 $(d_1, d_2, \text{combinedDiameter})$ 중 최댓값을 반환

이 로직으로,

return max({diameter1, diameter2, combinedDiameter});

하게 됩니다.

추가 참고:

• “왜 합친 트리의 직경에 $\lceil d_1/2\rceil + \lceil d_2/2\rceil + 1$?”
  • 각 트리의 지름 경로를 양끝이 아니라 중간에서 이어야 합쳐진 전체 경로가 가장 짧아지기 때문입니다.
  • 지름이 홀수일 땐 가운데가 간선 사이이므로 “$\lceil d/2\rceil$” 처리를 해 줍니다.
• 이렇게 구한 합쳐진 트리의 최소 지름과, 각 트리 자체 직경 가운데 최댓값을 최종적으로 반환하는 것이 본 코드의 의미입니다.

Approach 3: Topological Sorting

• 256ms, 296.14MB
• Complexity
  • Let $n$ be the number of nodes in the first tree and $m$ the number of nodes in the second tree.
  • Time Complexity: $O(n + m)$
  • Space Complexity: $O(n + m)$

class Solution {
public:
    int minimumDiameterAfterMerge(vector<vector<int>>& edges1,
                                  vector<vector<int>>& edges2) {
        // Calculate the number of nodes for each tree (number of edges + 1)
        int n = edges1.size() + 1;
        int m = edges2.size() + 1;

        // Build adjacency lists for both trees
        vector<vector<int>> adjList1 = buildAdjList(n, edges1);
        vector<vector<int>> adjList2 = buildAdjList(m, edges2);

        // Calculate the diameter of both trees
        int diameter1 = findDiameter(n, adjList1);
        int diameter2 = findDiameter(m, adjList2);

        // Output the diameters for debugging (can be removed in production
        // code)
        cout << diameter1 << " " << diameter2 << "\n";

        // Calculate the longest path that spans across both trees.
        int combinedDiameter =
            ceil(diameter1 / 2.0) + ceil(diameter2 / 2.0) + 1;

        return max({diameter1, diameter2, combinedDiameter});
    }

private:
    // Helper function to build an adjacency list from an edge list
    vector<vector<int>> buildAdjList(int size, vector<vector<int>>& edges) {
        vector<vector<int>> adjList(size);
        for (auto& edge : edges) {
            adjList[edge[0]].push_back(edge[1]);
            adjList[edge[1]].push_back(edge[0]);
        }
        return adjList;
    };

    // Function to find the diameter of a tree using topological sorting
    int findDiameter(int n, vector<vector<int>>& adjList) {
        queue<int> leavesQueue;
        vector<int> degrees(n);
        // Initialize the degree of each node and add leaves (nodes with degree
        // 1) to the queue
        for (int node = 0; node < n; node++) {
            degrees[node] =
                adjList[node].size();  // Degree is the number of neighbors
            if (degrees[node] == 1) {
                leavesQueue.push(node);
            }
        }

        int remainingNodes = n;
        int leavesLayersRemoved = 0;

        // Process the leaves until there are 2 or fewer nodes remaining
        while (remainingNodes > 2) {
            int size = leavesQueue.size();  // Get the number of leaves to
                                            // remove in this iteration
            remainingNodes -= size;
            leavesLayersRemoved++;

            // Remove the leaves from the queue and update the degrees of their
            // neighbors
            for (int i = 0; i < size; i++) {
                int currentNode = leavesQueue.front();
                leavesQueue.pop();

                // Process the neighbors of the current leaf
                for (int neighbor : adjList[currentNode]) {
                    degrees[neighbor]--;  // Decrease the degree of the neighbor
                    if (degrees[neighbor] == 1) {
                        leavesQueue.push(
                            neighbor);  // If the neighbor becomes a leaf, add
                                        // it to the queue
                    }
                }
            }
        }

        // If exactly two nodes remain, return the diameter as twice the number
        // of layers of leaves removed + 1 (as the diameter will include the
        // final connecting edge)
        if (remainingNodes == 2) return 2 * leavesLayersRemoved + 1;

        return 2 * leavesLayersRemoved;
    }
};

GPT

아래 코드는 두 개의 트리(edges1, edges2)에 대해 각각 “리프 노드를 하나씩 제거하는 방식(Topological Trimming)” 으로 지름(diameter)을 구한 후, 두 트리를 한 간선으로 연결했을 때의 “합쳐진 트리 직경(최소화)”를 계산하여, 세 값 중 최댓값을 반환하는 알고리즘입니다.

---

코드 흐름 요약

int minimumDiameterAfterMerge(vector<vector<int>>& edges1,
                              vector<vector<int>>& edges2) {
    // 1) 각 트리의 노드 수
    int n = edges1.size() + 1;
    int m = edges2.size() + 1;

    // 2) 인접 리스트 구성
    vector<vector<int>> adjList1 = buildAdjList(n, edges1);
    vector<vector<int>> adjList2 = buildAdjList(m, edges2);

    // 3) 두 트리 각각 지름(diameter) 계산
    int diameter1 = findDiameter(n, adjList1);
    int diameter2 = findDiameter(m, adjList2);

    // (디버깅용 출력)
    cout << diameter1 << " " << diameter2 << "\n";

    // 4) 두 트리를 한 간선으로 연결했을 때의 "최소" 직경 계산
    //    지름 d1, d2 => 합쳐진 트리 직경 = ceil(d1/2) + ceil(d2/2) + 1
    int combinedDiameter = ceil(diameter1 / 2.0) + ceil(diameter2 / 2.0) + 1;

    // 5) 세 값 중 최댓값 반환
    return max({diameter1, diameter2, combinedDiameter});
}

이 때 핵심 로직은 findDiameter() 입니다. 이 함수는 “리프 노드(차수가 1인 노드)를 바깥에서부터 제거해나가는 방식”으로 트리의 지름을 계산합니다.

---

1. buildAdjList()

vector<vector<int>> buildAdjList(int size, vector<vector<int>>& edges) {
    vector<vector<int>> adjList(size);
    for (auto& edge : edges) {
        adjList[edge[0]].push_back(edge[1]);
        adjList[edge[1]].push_back(edge[0]);
    }
    return adjList;
}

• 주어진 edges를 통해 양방향 그래프(트리) 의 인접 리스트 adjList를 구성합니다.

---

2. 리프 트리밍 방식으로 지름 구하기: findDiameter()

int findDiameter(int n, vector<vector<int>>& adjList) {
    queue<int> leavesQueue;
    vector<int> degrees(n);

    // 1) 초기 각 노드 차수 계산, 차수=1인 노드를 leavesQueue에 넣기
    for (int node = 0; node < n; node++) {
        degrees[node] = adjList[node].size();
        if (degrees[node] == 1) {
            leavesQueue.push(node);
        }
    }

    int remainingNodes = n;
    int leavesLayersRemoved = 0;

    // 2) 리프(차수=1) 노드를 "밖에서부터" 한 겹씩 제거
    while (remainingNodes > 2) {
        int size = leavesQueue.size();  // 이번 라운드에서 제거할 리프 수
        remainingNodes -= size;
        leavesLayersRemoved++;

        // 2a) 리프 노드들을 큐에서 꺼내 제거
        for (int i = 0; i < size; i++) {
            int currentNode = leavesQueue.front();
            leavesQueue.pop();

            // 이 리프의 이웃(=부모 혹은 연결 노드)의 차수 1 감소
            for (int neighbor : adjList[currentNode]) {
                if (--degrees[neighbor] == 1) {
                    // 새로 차수=1이 된 노드 -> 다음 라운드의 리프
                    leavesQueue.push(neighbor);
                }
            }
        }
    }

    // 3) 남은 노드 수(0,1,2)에 따라 지름 추정
    //  - 2개 남으면 "중심 노드가 2개"이므로 지름 = 2*layers + 1
    //  - 1개 이하 남으면 지름 = 2*layers
    if (remainingNodes == 2) {
        return 2 * leavesLayersRemoved + 1;
    }
    // remainingNodes == 1 or 0
    return 2 * leavesLayersRemoved;
}

핵심 아이디어

1. 트리의 지름을 구하는 또 다른 방법:
   • 가장 바깥(리프)부터 한 층씩 벗겨내는 “양파껍질 제거” 방식.
   • 트리에서 차수가 1인 노드(리프)를 큐에 넣고, 한 라운드마다 이 리프들을 제거.
   • 이웃 노드 차수를 갱신해, 새로 리프가 된 노드를 큐에 넣는다.
   • 이 “한 라운드” 가 “바깥에서부터 1 레벨(depth)을 제거”한 것과 같아서, 제거 횟수(layersRemoved) 를 통해 지름을 추정할 수 있습니다.
2. 왜 2개 노드 이하가 남을 때까지?
   • 트리 지름의 “중심”은 1개 노드(짝수 지름) 또는 2개 노드(홀수 지름)일 수 있음.
   • 중심(코어)에 2개 이하 노드가 남으면, 거기가 트리 지름의 중앙입니다.
3. 남은 노드가 2개인 경우 → 지름은 2*layers + 1
   • 예: 만약 홀수 지름이면, 중심이 2개 노드에 걸쳐 있고, 각 라이어(껍질)를 2번씩 이동해야 하는데 마지막에 “1”이 더해짐.
4. 남은 노드가 1개이거나 0개인 경우 → 지름은 2*layers
   • 짝수 지름. 중심이 하나의 노드이므로, 껍질 2 레이어씩 왕복 느낌(한 층 제거할 때마다 양쪽에서 1씩 소모).

---

3. 두 트리를 연결한 최소 직경 계산

int combinedDiameter = ceil(diameter1 / 2.0)
                    + ceil(diameter2 / 2.0)
                    + 1;

• 잘 알려진 그리디 아이디어:
  • 트리1 지름 = $d_1$, 트리2 지름 = $d_2$.
  • 각 지름 경로의 중앙(혹은 중앙 노드들)끼리 연결 → 합쳐진 트리의 직경이
    $\bigl\lceil d_1 / 2 \bigr\rceil \;+\; \bigl\lceil d_2 / 2 \bigr\rceil \;+\; 1$ 로 최소화됨.

---

4. 최종 결과

return max({diameter1, diameter2, combinedDiameter});

• 단독 트리1의 지름, 단독 트리2의 지름, 합쳐진 트리의 (최소) 지름
• 이 셋 중 최댓값을 최종 반환.

---

정리

1. 지름 계산:
   • 전통적으로 2번 BFS/DFS로 지름을 구할 수 있지만, 여기서는 “리프부터 레이어를 제거” 하는 방식을 사용.
   • 제거한 레이어 수(layersRemoved)로 지름을 추정:
     • 남은 노드가 2개이면 지름 = 2*layers + 1
     • 남은 노드가 1개 이하이면 지름 = 2*layers
2. 두 트리 합쳐서 직경 최소화:
   • 지름들이 $d_1, d_2$일 때, $\lceil d_1/2\rceil + \lceil d_2/2\rceil + 1$.
3. 최종: 세 후보($d_1, d_2, \text{combinedDiameter}$) 중 최댓값 반환.

이로써, 두 트리를 하나의 간선으로 연결했을 때 생길 수 있는 “최소 직경”과, 각각의 트리 직경을 한꺼번에 비교해 원하는 값을 얻는 로직이 완성됩니다.