题解 | 紧急疏散

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

class Solution {
private:
    vector<vector<int>> graph;
    vector<int> size;
    vector<int> depth;
    
    void dfs(int u, int parent, int d) {
        size[u] = 1;
        depth[u] = d;
        
        for (int v : graph[u]) {
            if (v != parent) {
                dfs(v, u, d + 1);
                size[u] += size[v];
            }
        }
    }
    
public:
    int getMinTime(int n, vector<vector<int>>& edges) {
        // 构建邻接表
        graph.resize(n + 1);
        size.resize(n + 1);
        depth.resize(n + 1);
        
        for (const auto& edge : edges) {
            int x = edge[0], y = edge[1];
            graph[x].push_back(y);
            graph[y].push_back(x);
        }
        
        // 计算每个子树的大小和深度
        dfs(1, 0, 0);
        
        // 计算最大疏散时间
        int maxTime = 0;
        for (int i = 2; i <= n; i++) {
            maxTime = max(maxTime, depth[i] + size[i] - 1);
        }
        
        return maxTime;
    }
};

int main() {
    int n;
    cin >> n;
    
    vector<vector<int>> edges;
    for (int i = 0; i < n - 1; i++) {
        int x, y;
        cin >> x >> y;
        edges.push_back({x, y});
    }
    
    Solution solution;
    cout << solution.getMinTime(n, edges) << endl;
    
    return 0;
}

import java.util.*;

public class Main {
    static class Solution {
        private List<List<Integer>> graph;
        private int[] size;
        private int[] depth;
        
        private void dfs(int u, int parent, int d) {
            size[u] = 1;
            depth[u] = d;
            
            for (int v : graph.get(u)) {
                if (v != parent) {
                    dfs(v, u, d + 1);
                    size[u] += size[v];
                }
            }
        }
        
        public int getMinTime(int n, int[][] edges) {
            // 构建邻接表
            graph = new ArrayList<>();
            for (int i = 0; i <= n; i++) {
                graph.add(new ArrayList<>());
            }
            size = new int[n + 1];
            depth = new int[n + 1];
            
            for (int[] edge : edges) {
                int x = edge[0], y = edge[1];
                graph.get(x).add(y);
                graph.get(y).add(x);
            }
            
            // 计算每个子树的大小和深度
            dfs(1, 0, 0);
            
            // 计算最大疏散时间
            int maxTime = 0;
            for (int i = 2; i <= n; i++) {
                maxTime = Math.max(maxTime, depth[i] + size[i] - 1);
            }
            
            return maxTime;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        int[][] edges = new int[n - 1][2];
        for (int i = 0; i < n - 1; i++) {
            edges[i][0] = sc.nextInt();
            edges[i][1] = sc.nextInt();
        }
        
        Solution solution = new Solution();
        System.out.println(solution.getMinTime(n, edges));
        
        sc.close();
    }
}

import sys
sys.setrecursionlimit(100005)
from collections import defaultdict

class Solution:
    def __init__(self):
        self.graph = defaultdict(list)
        self.size = []
        self.depth = []
        
    def dfs(self, u, parent, d):
        self.size[u] = 1
        self.depth[u] = d
        
        for v in self.graph[u]:
            if v != parent:
                self.dfs(v, u, d + 1)
                self.size[u] += self.size[v]
    
    def getMinTime(self, n, edges):
        self.size = [0] * (n + 1)
        self.depth = [0] * (n + 1)
        
        for x, y in edges:
            self.graph[x].append(y)
            self.graph[y].append(x)
        
        self.dfs(1, 0, 0)
        
        max_time = 0
        for i in range(2, n + 1):
            max_time = max(max_time, self.depth[i] + self.size[i] - 1)
            
        return max_time

# Read input
n = int(input())
edges = []
for _ in range(n - 1):
    x, y = map(int, input().split())
    edges.append([x, y])

solution = Solution()
print(solution.getMinTime(n, edges))