题干：

链接：https://ac.nowcoder.com/acm/contest/157/B
来源：牛客网

题目描述

    传说，凤凰是百鸟之王。有一天，凤凰要召开百鸟大会，百鸟国是一个由n个节点组成的树，每个节点有一只鸟，开会的节点定在1号节点。每只鸟可以花费1s通过一条边，由于每根树枝(边)的载重有限，只允许一只鸟同时通过。作为会议的策划师，HtBest想知道百鸟国的所有鸟在1点集合最少需要多少秒。

输入描述:

第一行有一个正整数n，表示百鸟国节点个数。
接下来n-1行，第i行两个正整数ai,bi用空格隔开，表示树上节点ai,bi之间有一条边。

输出描述:

第一行一个整数，表示集合最少需要的时间。

示例1

输入

复制

3
1 2
2 3

输出

复制

2

示例2

输入

复制

3
1 2
1 3

输出

复制

1

示例3

输入

复制

4
1 2
2 3
2 4

输出

复制

3

备注:

对于100%的测试数据：
1 ≤ n ≤ 1000000
数据量较大，注意使用更快的输入输出方式。

解题报告：

   这题用dfs会超时我也不知道为什么。O(n)的复杂度。。。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 2e6 + 5;
int n,m;
vector<int> vv[MAX];
int dfs(int cur,int rt) {
	int res = 1;
	for(auto& v : vv[cur]) {
		if(v == rt) continue;
		res += dfs(v,cur);
	}
	return res;
} 
inline int read() {
    char ch = getchar(); int x = 0, f = 1;
    while(ch < '0' || ch > '9') {
        if(ch == '-') f = -1;
        ch = getchar();
    } while('0' <= ch && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    } return x * f;
}
int f[MAX],num[MAX];
int getf(int v) {
	return f[v] == v ? v : f[v] = getf(f[v]);
}  
bool merge(int u,int v) {
	int  t1 = getf(u);
	int t2 = getf(v);
	if(t1 == t2) {
		return 1;
	}
	else {
		f[t2] = t1;
		num[t1] += num[t2];
		return 0 ;
	}
}
int main()
{
	cin>>n;
	for(int i = 1; i<=n; i++) f[i] = i,num[i]=1;
	for(int a,b,i = 1; i<=n-1; i++) {
		a=read();b=read();
		if(a!=1 && b!=1) merge(a,b);
	}
	int ans = 0 ;
	for(int i = 1; i<=n; i++) {
		ans = max(ans,num[getf(i)]);
	}
	cout << ans;
	return 0;
}

TLE代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 2e6 + 5;
int n,m;
vector<int> vv[MAX];
int dfs(int cur,int rt) {
    int res = 1;
    for(auto v : vv[cur]) {
        if(v == rt) continue;
        res += dfs(v,cur);
    }
    return res;
}
int main()
{
    cin>>n;
    for(int a,b,i = 1; i<=n-1; i++) {
        scanf("%d%d",&a,&b);
        vv[a].pb(b);
        vv[b].pb(a);
    }
    int ans = 0 ;
    for(auto v : vv[1]) {
        ans = max(ans,dfs(v,1));
    }
    cout << ans;
    return 0;
}