描述
体育场突然着火了，现场需要紧急疏散，但是过道真的是太窄了，同时只能容许一个人通过。现在知道了体育场的所有座位分布，座位分布图是一棵树，已知每个座位上都坐了一个人，安全出口在树的根部，也就是1号结点的位置上。其他节点上的人每秒都能向树根部前进一个结点，但是除了安全出口以外，没有任何一个结点可以同时容纳两个及以上的人，这就需要一种策略，来使得人群尽快疏散，问在采取最优策略的情况下，体育场最快可以在多长时间内疏散完成。
输入描述：
第一行包含一个正整数n，即树的结点数量（1<=n<=100000）。 接下来有n-1行，每行有两个正整数x，y，表示在x和y结点之间存在一条边。(1<=x，y<=n)
输出描述：
输出仅包含一个正整数，表示所需要的最短时间
思路：；
这个题就是一个求最大，这里用并查集解决。
f 数组：查找集合元素时，将会递归定位到此集合最后插入的元素
cnt数组：当第 i 个元素插入集合时，这个集合中元素的个数
1 #include <vector> 2 #include <stdio.h> 3 4 using namespace std; 5 // 使用并查集求出各个子树的最大节点数，即为最后结果 6 struct DSU { 7 vector<int> f, cnt; 8 DSU(int n) : f(n), cnt(n, 1) { 9 for (int i = 0; i < n; i++) 10 f[i] = i; 11 } 12 13 int find(int x) { 14 if (f[x] == f[f[x]]) return f[x]; 15 return f[x] = find(f[x]); 16 } 17 bool merge(int x, int y) { 18 int fx = find(x), fy = find(y); 19 if (fx == fy) return false; 20 f[fy] = fx; 21 cnt[fx] += cnt[fy]; 22 return true; 23 } 24 }; 25 26 int main() { 27 int n; 28 scanf("%d", &n); 29 DSU dsu(n+1); 30 31 vector<int> root; 32 for (int i = 1; i < n; i++) { 33 int a, b; 34 scanf("%d%d", &a, &b); 35 if (a == 1) root.push_back(b); 36 else if (b == 1) root.push_back(a); 37 else dsu.merge(a, b); 38 } 39 int ans = 0; 40 for (int a : root) ans = max(ans, dsu.cnt[dsu.find(a)]); 41 printf("%d ", ans); 42 return 0; 43 44 }