J 树上行走

J 树上行走

并查集，将连边的点连起来，将连边的点连起来，写一个循环让它们的根，再通过这个根的最大值，找它的子节点。

用的出题人大佬的板

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;

int fa[maxn],sz[maxn],col[maxn];
int find(int x){
    if(fa[x]==x)return x;
    return fa[x]=find(fa[x]);
}

int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",col+i);
        fa[i]=i;
    }
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        if(col[u]==col[v])fa[find(u)]=find(v);
    }
    set<int> ans;
    int mx=0;
    for(int i=1;i<=n;i++){
        sz[find(i)]++;
        mx=max(mx,sz[find(i)]);
    }
    for(int i=1;i<=n;i++)
        if(sz[find(i)]==mx)ans.insert(i);
    printf("%d\n",ans.size());
    for(auto i:ans)printf("%d ",i);
    return 0;
}