牛客小白月赛25 C-白魔法师 ( 图论 + 并查集 )

题目链接

解题报告：
思路：如果将一个黑色点染成白色，那么将得到一个白色连通块，这个连通块由和这个黑色点连结的所有白色连通块组成。
如果将一个白色点染成白色，那么不会有任何变化。
所以我们可以先并查集预处理一下，把所有白色连通块的大小求出来，并把所有白色点对应的连通块表示一下。连通块的大小可以dfs或者统计并查集根的孩子总数得出。
然后统计所有黑色点的邻点连通块大小即可。要注意特判全部是白色点的情况

#define first f
#define second s
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define sl(p) strlen(p)
#define SZ(p) p.size()
#include <bits/stdc++.h>
#define lb lower_bound
#define ub upper_bound
#define mem(a,b) memset(a,b,sizeof(a))
#define fast_cin  ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
using namespace std;
const ll MOD=1e9+7;
const int maxn=1e5+5;
const int inf=0x3f3f3f3f;
const long double eps=1e-8;

int sz[maxn],sm[maxn],f[maxn];
vector<int>g[maxn];
char p[maxn];
int getfind(int x)
{
    return f[x]==x?x:f[x]=getfind(f[x]);
}
void Union(int x,int y)
{
    x=getfind(x),y=getfind(y);
    if(x!=y){
        if(sm[x]<sm[y]) f[x]=y,sm[y]+=sm[x];
        else f[y]=x,sm[x]+=sm[y];
    }
}
int main()
{
    int n,u,v;
    scanf("%d%s",&n,p+1);
    for(int i=1;i<=n;i++) sm[i]=1,f[i]=i;
    for(int i=1;i<n;i++){
        scanf("%d%d",&u,&v);
        g[u].pb(v);g[v].pb(u);
        if(p[u]=='W'&&p[v]=='W') Union(v,u);
    }
    for(int i=1;i<=n;i++) sz[i]=sm[getfind(i)];
    int ans=-1;
    for(int i=1;i<=n;i++){
        if(p[i]=='B'){
            int res=1;
            for(int j=0;j<SZ(g[i]);j++){
                if(p[g[i][j]]=='W') res+=sz[g[i][j]];
            }
            ans=max(ans,res);
        }
    }
    printf("%d\n",ans==-1?n:ans);
    return 0;
}