C++(g++ 7.5.0) 解法, 执行用时: 338ms, 内存消耗: 6932K, 提交时间: 2023-03-19 13:51:33

#include <iostream>
#include <vector>
#include <cstring>
#define ll long long
#define endl '\n'
using namespace std;
const int N=1e5+8;
ll u,v,n,sum;
string c;
vector<ll>e[N];
bool vis[N];
void dfs(ll x){
	sum++;
	vis[x]=1;
	for(ll i=0;i<e[x].size();i++){
		if(!vis[e[x][i]]&&c[e[x][i]-1]=='W'){
			dfs(e[x][i]);
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	cin>>c;
	for(ll i=1;i<n;i++){
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u); 
	}
	ll ans=0;
	for(ll i=1;i<=n;i++){
		if(!vis[i]&&c[i-1]=='W'){
			sum=0;
			dfs(i);
			ans=max(ans,sum);
		}else if(!vis[i]&&c[i-1]=='B'){
			memset(vis,0,sizeof(vis));
			sum=0;
			dfs(i);
			ans=max(ans,sum);
		}
	}
	cout<<ans<<endl;
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 55ms, 内存消耗: 6988K, 提交时间: 2020-05-19 11:19:03

#include<bits/stdc++.h>
using namespace std;
const int mx=1e5+4;
char s[mx];
vector<int> v[mx];
int f[mx],k[mx];
int find(int x){
	if(f[x]==x)return x;
	return f[x]=find(f[x]);
}
void uni(int &a,int &b){
	int fa=find(a),fb=find(b);
	if(fa!=fb)f[fa]=fb,k[fb]+=k[fa];
}
int main(){
	int n;scanf("%d",&n);
	scanf("%s",s+1);
	for(int i=1;i<=n;++i)
		f[i]=i,k[i]=1;
	for(int a,b,i=1;i<n;++i){
		scanf("%d%d",&a,&b);
		v[a].push_back(b);
		v[b].push_back(a);
		if(s[a]=='W'&&s[b]=='W')uni(a,b);
	}
	int ans=0;
	for(int i=1;i<=n;++i)
		if(s[i]=='B'){
			int may=0;
			for(int j=0,en=v[i].size();j<en;++j)
				if(s[v[i][j]]=='W')may+=k[find(v[i][j])];
			ans=max(ans,may+1);
		}
	if(!ans)ans=n;
	printf("%d",ans);
}

C++ 解法, 执行用时: 228ms, 内存消耗: 7384K, 提交时间: 2022-02-25 23:03:25

#include <bits/stdc++.h>
using namespace std;
int n;
char s[100010];
int x, y;
vector<int> mp[100010];
int ans = 0;
void dfs(int now, int pre) {
	ans++;
	for (auto t : mp[now]) {
		if (t != pre && s[t] == 'W') {
			dfs(t, now);
		}
	}
}

int main() {
	scanf("%d", &n);
	scanf("%s", s + 1);
	for (int i = 0; i < n - 1; i++) {
		scanf("%d%d", &x, &y);
		mp[x].push_back(y);
		mp[y].push_back(x);
	}
	int res = 0;
	for (int i = 1; i <= n; i++) {
		if (s[i] == 'B') {
			ans = 0;
			dfs(i, -1);
			res = max(ans, res);
		}
	}
	if (!res)
		printf("%d\n", n);
	else
		printf("%d\n", res);
	return 0;
}