牛客·凤凰（https://ac.nowcoder.com/acm/contest/26908/1006）

并查集
//这个题就是求1为主干的分支中，分支的子树节点最多的
//对于1为父亲的子节点，子节点到1这条路径总会有鸟走（除非最后一只鸟到达了1）
//它的子节点会代替它，时间差只为一秒，所以，一个走一个补上，总会有鸟，所以是连续的
//这样看，只需要看1的子树的节点数量，数量最多的为答案（各子树不会冲突）
1
2
3
4
5

#include
using namespace std;
#define int long long
int n;
int b[2000005],a[1000006];
int find(int x){return x==b[x]?x:b[x]=find(b[x]);}//递归把x=b[x];

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=0;i<=n;i++)b[i]=i;
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        if(x==1||y==1)continue;
        int fx=find(x);
        int fy=find(y);
        if(fx!=fy)b[fx]=fy;
    }
    int ans=0;
    for(int i=2;i<=n;i++)
    {
        int fx=find(i);
        a[fx]++;
        ans=max(ans,a[fx]);
    }
    cout<<ans<<'\n';
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31