题目链接

https://ac.nowcoder.com/acm/contest/7412/J

题目大意

挺明了的吧。

解题思路

并查集！挺明显的吧。
连通的区域属于一个整体，这种类型就用并查集。
如果不知道并查集，看看这个
于本题而言，
S1：把相同类型结点之间的边join一下，不同类型结点之间即使有边，我们也不join，因为不同类型的结点根本不可能属于一个连通区域。
S2：可是现在并非同属于一个连通区域的结点的根都相同，不信的话你可以跑一下AC代码下面注释掉的样例，结点1，2，3，4应该是相连的，即同属于一个连通区域，但是，如果循环输出fa的话会发现并非他们的fa都存的同一个结点，所以结果也出现了问题。
解决此问题，就需要对每个点再刷新一次他们的根节点，要让同一连通区域内的结点的根节点为同一个点。代码实现：循环每个结点，用find去刷新根节点。
S3：最后一步就是找到最大连通区域内的全部点（此区域可能不止一个）。
这应该比较好找，有很多方式去找，这里我感觉我用了好几个循环比较麻烦，但是想了好久也没想出来有什么简单的方法或者容器去实现。因为我写的比较繁琐，所以建议大家自己想，自己写，这样思路清晰，不用看我这繁琐的代码，不宜读懂。（自己实在不会可以看看我的讲解）
我的实现原理：
第一个循环，遍历所有结点，找到他们的根节点，cnt存储某个根节点出现的次数，同时确定最多出现了多少次；
第二个循环，遍历所有结点，如果当前结点的根节点出现次数等于上个第一个循环中统计的最多次数，说明当前遍历到的结点属于某个最大连通区域，所以把此点记录在ans数组中，同时num用于控制ans的存储点的个数。此时放入ans数组中的结点一定是按照从小到大存放的，因为我们是从小到大遍历的。
输出num，即数量。
第三个循环，把ans内的点输出。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=200010;
int fa[N],type[N],cnt[N],ans[N];
int n,u,v,maxx,num;
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void join(int x,int y){
    int rx=find(x),ry=find(y);
    if(rx!=ry) fa[rx]=ry;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=n;i++) cin>>type[i];//存储结点的类型
//---------------------------S1-------------------------------
    for(int i=1;i<n;i++){
        cin>>u>>v;
        if(type[u]==type[v]) join(u,v);//类型相同的结点，join一下
    }
//---------------------------S2-------------------------------
    for(int i=1;i<=n;i++) fa[i]=find(i);//S2过程，刷新根结点//少了这句过93的数据，泪的教训！
//---------------------------S3-------------------------------
    for(int i=1;i<=n;i++) cnt[fa[i]]++,maxx=max(maxx,cnt[fa[i]]);//第一个循环
    for(int i=1;i<=n;i++) if(cnt[fa[i]]==maxx) ans[++num]=i;//第二个循环
    cout<<num<<endl;
    for(int i=1;i<num;i++) cout<<ans[i]<<' ';cout<<ans[num]<<endl;//第三个循环
}
/*
特殊样例
4
1 1 1 1
1 2
2 3
3 4
*/