Language: C++

#include<iostream>

#include <vector>
#include <list>
#include<stack>
#include<queue>
#include<array>

#include <set>
#include<map>

#include<string>
#include<stdlib.h>

#include<algorithm>
#include <functional>
#include<math.h>

#include<fstream>
#include<iomanip>

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int,int>;

#define FOR(k,m,n) for(ll (k)=(m);(k)<(n);(k)++)
#define REP(i,n) FOR((i),0,(n))
#define WAITING(str) int str;std::cin>>str;
#define DEBUGING(str) cout<<str<<endl

constexpr int INF = (1 << 30);
constexpr ll INFL = (1ll << 60);
constexpr ll MOD = 1000000007;// 10^9+7


//変数
int N;
vector<set<int>> edges;
vector<bool> black;
vector<int> d;



//サブ関数
//入力
void input()
{
	cin >> N;
	edges.resize(N);
	d.resize(N);
	int x, y;
	REP(i, N-1) {
		cin >> x >> y;
		x--; y--;
		edges[x].insert(y);
		edges[y].insert(x);
	}
	string cs;
	cin >> cs;
	for (auto c : cs)black.push_back((c == 'B'));
}

using pis = pair<int, set<int>*>;
auto c = [](const pis o1, const pis o2)
{
	return (o1.second->size()) > (o2.second->size());
};
using PQ = priority_queue<pis, vector<pis>, decltype(c)>;

void cut_reaf()
{
	PQ pq(c);
	REP(i, N)pq.push({ i,&edges[i] });
	while (!pq.empty()) {
		auto reaf = pq.top(); pq.pop();
		if (reaf.second->size() >= 2)break;
		if (!black[reaf.first])continue;
		int now = reaf.first;
		for (const auto& next : edges[now]) {
			edges[next].erase(now);
		}
		edges[now].clear();
	}
}

int normal_count()
{
	int res = 0;
	REP(i, N) {
		const auto& edge = edges[i];
		if (edge.empty()) continue;
		REP(j, (int)edge.size()) {
			black[i] = !black[i];
			res++;
		}
	}
	return res;
}

void bfs(int s) {
	fill(d.begin(), d.end(), INF);
	queue<int>Q;
	Q.push(s);
	d[s] = 0;
	int u;
	while (!Q.empty()) {
		u = Q.front(); Q.pop();
		for (const int to : edges[u]) {
			if (d[to] != INF)continue;
			d[to] = d[u] + (black[to] ? 0 : 1);
			Q.push(to);
		}
	}
	for (auto& tmp : d)if (tmp == INF)tmp = -1;
}

int back_trace(int s) {
	int res = 0;
	if (!black[s]) {
		black[s] = true;
		res++;
	}
	set<int> best;
	queue<pair<int, set<int>>> q;
	q.push({ s, set<int>() });
	while (true) {
		auto now = q.front(); q.pop();
		for (const int to : edges[now.first]) {
			if (d[to] == 0) {
				now.second.insert(now.first);
				now.second.insert(to);
				best = now.second;
				goto last;
			}
			if ((d[to] <= d[now.first]) && 
				(now.second.find(to) == now.second.end())
				) {
				pair<int, set<int>> next = { to,now.second };
				next.second.insert(now.first);
				q.push(next);
			}
		}
	}
last:;
	for (int p : best) {
		if (!black[p]) {
			black[p] = true;
			res++;
		}
	}
	return res;
}

int last_switch() {
	int res = 0;
	for (auto& f : black)if (!f)res++;
	return res;
}

//計算
void calc()
{
	cut_reaf();
	int res = normal_count();
	int start = -1;
	REP(i, N)if (!edges[i].empty())start = i;
	if (start != -1) {
		bfs(start);
		start = distance(d.begin(), max_element(d.begin(), d.end()));
		bfs(start);
		start = distance(d.begin(), max_element(d.begin(), d.end()));

		res -= back_trace(start);
		res += last_switch();
	}
	cout << res << endl;
}


//出力
void output()
{

}


//デバッグ
void debug()
{
	int N;
	cin>>N;
}


//メイン関数
int main()
{
	input();
	calc();
	output();
	debug();
	
	return 0;
}


Compiler output:
a.cc: In function 'int last_switch()':
a.cc:157:24: error: cannot bind non-const lvalue reference of type 'std::_Bit_reference&' to an rvalue of type 'std::_Bit_iterator::reference'
  157 |         for (auto& f : black)if (!f)res++;
      |                        ^~~~~