stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

#define MAXN 100000

#define rint register int

inline int read(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}

vector<int> e[MAXN+5]; int s[MAXN+5], c[MAXN+5], n, r, f, m, Ans; string S = "B", _;

void DFS(int p, int fa){s[p] = S[p]=='W', c[p] = (S[p]!='B')^!!fa; for(auto v:e[p]) if(v^fa) DFS(v,p), s[p] += s[v], c[p] ^= !!s[v];}

void Dia(int p, int fa, int d){d>m||(d==m&&!c[p])?m=d,f=p:0; for(auto v:e[p]) if(s[v]&&v^fa) Dia(v,p,d+(c[v]<<1));}

void Cal(int p, int fa){Ans += c[p]; for(auto v:e[p]) if(s[v]&&v^fa) Cal(v,p), Ans += 2;}

int main()

{

	n = read(); for(rint i = 2, a, b; i <= n; a = read(), b = read(), e[a].push_back(b), e[b].push_back(a), i++); cin >> _, S = S+_;

	if(~(r=S.find('W'))) DFS(r,0), Cal(r,0), Dia(f=r,0,m=c[r]<<1), Dia(r=f,0,m=c[f]<<1), Ans -= m-((c[r]&&c[f])<<1); return !printf("%d\n",Ans);

}

// Faster C++ solution for the same problem (measured speedup: 3.5701437236465505x):
#include<bits/stdc++.h>

#define reg register

typedef long long ll;

using namespace std;

const int MN=1e5+5;

int to[MN<<1],nxt[MN<<1],deg[MN],h[MN],cnt;

inline void ins(int s,int t){

	to[++cnt]=t;nxt[cnt]=h[s];h[s]=cnt;deg[t]++;

	to[++cnt]=s;nxt[cnt]=h[t];h[t]=cnt;deg[s]++;

}

bool t[MN],vis[MN];

char ch[MN];

int n,ans,sum,que[MN],f[MN];

void dfs(int st,int fa=0){

	sum+=deg[st];sum+=(deg[st]=(!t[st])^(deg[st]&1));

	for(reg int i=h[st];i;i=nxt[i])

		if(!vis[to[i]]&&to[i]!=fa){

			dfs(to[i],st);ans=min(ans,f[st]+f[to[i]]);

			f[st]=min(f[st],f[to[i]]-2*deg[st]);

		}

}

int main(){

	scanf("%d",&n);reg int he=0,ta=0;

	for(reg int i=1,s,t;i<n;i++)scanf("%d%d",&s,&t),ins(s,t);

	scanf("%s",ch+1);

	for(reg int i=1;i<=n;i++)t[i]=(ch[i]=='B');

	for(reg int i=1;i<=n;i++)if(deg[i]<2&&t[i])que[ta++]=i;

	while(he<ta){

		reg int v=que[he++];vis[v]=true;

		for(reg int i=h[v];i;i=nxt[i])if((--deg[to[i]])==1&&t[to[i]])que[ta++]=to[i];

	}

	if(ta==n)return 0*puts("0");

	for(reg int i=1;i<=n;i++)

		if(!vis[i]&&!t[i]){

			dfs(i);return 0*printf("%d\n",sum+ans);

		}

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;



#define CO const

#define IN inline

typedef long long int64;



template<class T> IN T read(){

	T x=0,w=1;char c=getchar();

	for(;!isdigit(c);c=getchar())if(c=='-') w=-w;

	for(;isdigit(c);c=getchar()) x=x*10+c-'0';

	return x*w;

}

template<class T> IN T read(T&x){

	return x=read<T>();

}



CO int N=2e5+10;

vector<int> to[N];

int deg[N];

char str[N];

int tag[N],tot;

int val[N],p;

int dp[N][2],f[N];



void check(int u,int fa){

	if(str[u]=='W') tag[u]=1;

	for(int v:to[u])if(v!=fa){

		check(v,u);

		if(!tag[v]) --deg[u],--deg[v];

		tag[u]|=tag[v];

	}

	tot+=tag[u];

}

void dfs(int u,int fa){

	f[u]=2*(tot-1)+p;

	dp[u][0]=val[u]?-1:1;

	for(int v:to[u])if(v!=fa and tag[v]){

		dfs(v,u);

		f[u]=min(f[u],f[v]);

		f[u]=min(f[u],2*(tot-1)+p-dp[u][0]-dp[v][1]-1);

		f[u]=min(f[u],2*(tot-1)+p-dp[u][1]-dp[v][0]-1);

		dp[u][0]=max(dp[u][0],dp[v][0]+1+(val[u]?-1:1));

		dp[u][1]=max(dp[u][1],dp[v][1]+1+(val[u]?-1:1));

	}

}

int main(){

	int n=read<int>();

	for(int i=1;i<n;++i){

		int u=read<int>(),v=read<int>();

		to[u].push_back(v),to[v].push_back(u);

		++deg[u],++deg[v];

	}

	scanf("%s",str+1);

	int rt=0;

	for(int i=1;i<=n;++i)if(str[i]=='W') rt=i;

	check(rt,0);

	for(int i=1;i<=n;++i)if(tag[i]) val[i]=(str[i]=='B')^(deg[i]&1),p+=!val[i];

	dfs(rt,0);

	printf("%d\n",!tot?tot:f[rt]);

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.810625069223477x):
#include <bits/stdc++.h>

using namespace std;

const int MAXN=100100;

vector<int> arr[MAXN];

char ch[MAXN];

int col[MAXN],deg[MAXN],val[MAXN],can[MAXN];

int f[MAXN],g[MAXN];

int n,root,sum,rest;

inline void dfs(register int now,register int pre)

{

	can[now]=col[now];

	for(register int i=0;i<(int)arr[now].size();i++)

		if(arr[now][i]!=pre)

		{

			dfs(arr[now][i],now);

			can[now]&=can[arr[now][i]];

			if(!can[arr[now][i]]) deg[now]++,deg[arr[now][i]]++;

		}

	return;

}

inline void solve(register int now,register int pre)

{

//	cout<<now<<" "<<pre<<endl;

	sum+=deg[now];

	if((deg[now]+col[now])&1) val[now]=0;

	else val[now]=2,sum++;

	register int fmax=0,gmax=0,flag=0;

	for(register int i=0;i<(int)arr[now].size();i++)

		if(arr[now][i]!=pre&&!can[arr[now][i]])

		{

			flag=1,solve(arr[now][i],now);

			rest=max(rest,max(f[arr[now][i]]+gmax,g[arr[now][i]]+fmax)+val[now]);

			fmax=max(fmax,f[arr[now][i]]),gmax=max(gmax,g[arr[now][i]]);

		}

	f[now]=fmax+val[now];

	if(flag) g[now]=gmax+val[now];

	else g[now]=-INT_MAX;

	return;

}

int main()

{

	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

	cin>>n;

	for(register int i=1,x,y;i<n;i++) cin>>x>>y,arr[x].push_back(y),arr[y].push_back(x);

	cin>>(ch+1);

	for(register int i=1;i<=n;i++)

	{

		col[i]=((ch[i]=='W')?0:1);

		if(!col[i]) root=i;

	}

	dfs(root,0);

	solve(root,0);

	cout<<(root?sum-rest:0)<<endl;

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;



#define CO const

#define IN inline

typedef long long int64;



template<class T> IN T read(){

	T x=0,w=1;char c=getchar();

	for(;!isdigit(c);c=getchar())if(c=='-') w=-w;

	for(;isdigit(c);c=getchar()) x=x*10+c-'0';

	return x*w;

}

template<class T> IN T read(T&x){

	return x=read<T>();

}



CO int N=2e5+10;

vector<int> to[N];

int deg[N];

char str[N];

int tag[N],tot;

int val[N],p;

int dp[N][2],f[N];



void check(int u,int fa){

	if(str[u]=='W') tag[u]=1;

	for(int v:to[u])if(v!=fa){

		check(v,u);

		if(!tag[v]) --deg[u],--deg[v];

		tag[u]|=tag[v];

	}

	tot+=tag[u];

}

void dfs(int u,int fa){

	f[u]=2*(tot-1)+p;

	dp[u][0]=val[u]?-1:1;

	for(int v:to[u])if(v!=fa and tag[v]){

		dfs(v,u);

		f[u]=min(f[u],f[v]);

		f[u]=min(f[u],2*(tot-1)+p-dp[u][0]-dp[v][1]-1);

		f[u]=min(f[u],2*(tot-1)+p-dp[u][1]-dp[v][0]-1);

		dp[u][0]=max(dp[u][0],dp[v][0]+1+(val[u]?-1:1));

		dp[u][1]=max(dp[u][1],dp[v][1]+1+(val[u]?-1:1));

	}

}

int main(){

	int n=read<int>();

	for(int i=1;i<n;++i){

		int u=read<int>(),v=read<int>();

		to[u].push_back(v),to[v].push_back(u);

		++deg[u],++deg[v];

	}

	scanf("%s",str+1);

	int rt=0;

	for(int i=1;i<=n;++i)if(str[i]=='W') rt=i;

	check(rt,0);

	for(int i=1;i<=n;++i)if(tag[i]) val[i]=(str[i]=='B')^(deg[i]&1),p+=!val[i];

	dfs(rt,0);

	printf("%d\n",!tot?tot:f[rt]);

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.8277521160462207x):
#include <bits/stdc++.h>

#define N 100005



using namespace std;



inline int input() {

	int x; char ch; while (!isdigit(ch = getchar()));

	for (x = ch ^ 48; isdigit(ch = getchar()); x = x * 10 + (ch ^ 48));

	return x;

}



template <class T> void chkmax(T &x, T y) { x = x > y ? x : y; }

template <class T> void chkmin(T &x, T y) { x = x < y ? x : y; }



int n;

int du[N], dp[N];

int val[N], res, cnt, tot;

bool c[N], del[N];

vector<int> G[N];

char s[N];



inline void AddEdge(int x, int y) {

	G[x].push_back(y), ++du[x];

	G[y].push_back(x), ++du[y];

}



void dfs(int u, int fa) {

	dp[u] = val[u];

	for (int v : G[u])

		if (v != fa && !del[v]) {

			dfs(v, u);

			chkmax(res, dp[u] + dp[v]);

			chkmax(dp[u], dp[v] + val[u]);

		}

}



int main() {

	n = input();

	for (int i = 1, u, v; i < n; ++i) {

		u = input(), v = input();

		AddEdge(u, v);

	}

	scanf("%s", s + 1);

	for (int i = 1; i <= n; ++i)

		c[i] = s[i] == 'B';

		

	queue<int> que;

	for (int i = 1; i <= n; ++i)

		if (c[i] && du[i] == 1) que.push(i);

	while (!que.empty()) {

		int u = que.front(); que.pop();

		del[u] = true, ++tot;

		for (int v : G[u])

			if ((--du[v]) == 1 && c[v]) que.push(v);

	}

	

	if (tot == n) return puts("0"), 0;



	for (int u = 1; u <= n; ++u) {

		if (del[u]) continue;

		if (c[u] ^ (du[u] & 1)) val[u] = 0;

		else val[u] = 2, ++cnt;

	}



	for (int i = 1; i <= n; ++i)

		if (!del[i]) {

			dfs(i, 0);

			break;

		}

	printf("%d\n", (n - tot) * 2 - 2 + cnt - res);

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

#define MAXN 100000

#define rint register int

inline int read(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}

vector<int> e[MAXN+5]; int s[MAXN+5], c[MAXN+5], n, r, f, m, Ans; string S = "B", _;

void DFS(int p, int fa){s[p] = S[p]=='W', c[p] = (S[p]!='B')^!!fa; for(auto v:e[p]) if(v^fa) DFS(v,p), s[p] += s[v], c[p] ^= !!s[v];}

void Dia(int p, int fa, int d){d>m||(d==m&&!c[p])?m=d,f=p:0; for(auto v:e[p]) if(s[v]&&v^fa) Dia(v,p,d+(c[v]<<1));}

void Cal(int p, int fa){Ans += c[p]; for(auto v:e[p]) if(s[v]&&v^fa) Cal(v,p), Ans += 2;}

int main()

{

	n = read(); for(rint i = 2, a, b; i <= n; a = read(), b = read(), e[a].push_back(b), e[b].push_back(a), i++); cin >> _, S = S+_;

	if(~(r=S.find('W'))) DFS(r,0), Cal(r,0), Dia(f=r,0,m=c[r]<<1), Dia(r=f,0,m=c[f]<<1), Ans -= m-((c[r]&&c[f])<<1); return !printf("%d\n",Ans);

}

// Faster C++ solution for the same problem (measured speedup: 3.541414295553105x):
# include <iostream>

# include <cstdio>

using namespace std;

const int N = 2e5 + 12;

const int inf = 0x3f3f3f3f;

int n,head[N],dt,du[N],bac[N],que[N],rt,a[N],tot,p;char str[N];bool w[N];

struct Edge{int to,nex;}edge[N << 1];

void Add(int u,int v){edge[++dt] = (Edge){v,head[u]};head[u] = dt;du[u]++;}

void Dfs(int u,int pre)

{

    if(str[u] == 'W')w[u] = true;

    for(int i = head[u];i;i = edge[i].nex)if(edge[i].to != pre)

    {

        Dfs(edge[i].to,u);

        if(!w[edge[i].to])du[u]--,du[edge[i].to]--;

        w[u] |= w[edge[i].to];

    }

    if(w[u])tot++;

}

void rebuild()

{

    for(int i = 1;i <= n;i++)if(str[i] == 'W')rt = i;

    Dfs(rt,-1);

    for(int i = 1;i <= n;i++)if(w[i])a[i] = (str[i] == 'B') ^ (du[i] & 1),p += !a[i];

}

int dp[N][2],f[N];

void dfs(int u,int pre)

{

    f[u] = (tot - 1) * 2 + p;

    dp[u][0] = a[u] ? -1 : 1;

    for(int i = head[u];i;i = edge[i].nex)if(edge[i].to != pre && w[edge[i].to])

    {

        dfs(edge[i].to,u);

        f[u] = min(f[u],f[edge[i].to]);

        f[u] = min(f[u],(tot - 1) * 2 + p - dp[u][0] - dp[edge[i].to][1] - 1);

        f[u] = min(f[u],(tot - 1) * 2 + p - dp[u][1] - dp[edge[i].to][0] - 1);

        dp[u][0] = max(dp[u][0],dp[edge[i].to][0] + 1 + (a[u] ? -1 : 1));

        dp[u][1] = max(dp[u][1],dp[edge[i].to][1] + 1 + (a[u] ? -1 : 1));

    }

}

int main()

{

    

    scanf("%d",&n);int x,y;

    for(int i = 1;i < n;i++)scanf("%d %d",&x,&y),Add(x,y),Add(y,x);

    scanf("%s",str + 1);rebuild();dfs(rt,-1);

    printf("%d\n",!tot ? tot : f[rt]);

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;



#define CO const

#define IN inline

typedef long long int64;



template<class T> IN T read(){

	T x=0,w=1;char c=getchar();

	for(;!isdigit(c);c=getchar())if(c=='-') w=-w;

	for(;isdigit(c);c=getchar()) x=x*10+c-'0';

	return x*w;

}

template<class T> IN T read(T&x){

	return x=read<T>();

}



CO int N=2e5+10;

vector<int> to[N];

int deg[N];

char str[N];

int tag[N],tot;

int val[N],p;

int dp[N][2],f[N];



void check(int u,int fa){

	if(str[u]=='W') tag[u]=1;

	for(int v:to[u])if(v!=fa){

		check(v,u);

		if(!tag[v]) --deg[u],--deg[v];

		tag[u]|=tag[v];

	}

	tot+=tag[u];

}

void dfs(int u,int fa){

	f[u]=2*(tot-1)+p;

	dp[u][0]=val[u]?-1:1;

	for(int v:to[u])if(v!=fa and tag[v]){

		dfs(v,u);

		f[u]=min(f[u],f[v]);

		f[u]=min(f[u],2*(tot-1)+p-dp[u][0]-dp[v][1]-1);

		f[u]=min(f[u],2*(tot-1)+p-dp[u][1]-dp[v][0]-1);

		dp[u][0]=max(dp[u][0],dp[v][0]+1+(val[u]?-1:1));

		dp[u][1]=max(dp[u][1],dp[v][1]+1+(val[u]?-1:1));

	}

}

int main(){

	int n=read<int>();

	for(int i=1;i<n;++i){

		int u=read<int>(),v=read<int>();

		to[u].push_back(v),to[v].push_back(u);

		++deg[u],++deg[v];

	}

	scanf("%s",str+1);

	int rt=0;

	for(int i=1;i<=n;++i)if(str[i]=='W') rt=i;

	check(rt,0);

	for(int i=1;i<=n;++i)if(tag[i]) val[i]=(str[i]=='B')^(deg[i]&1),p+=!val[i];

	dfs(rt,0);

	printf("%d\n",!tot?tot:f[rt]);

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 6.45272556044273x):
# include <iostream>

# include <cstdio>

using namespace std;

const int N = 2e5 + 12;

const int inf = 0x3f3f3f3f;

int n,head[N],dt,du[N],bac[N],que[N],rt,a[N],tot,p;char str[N];bool w[N];

struct Edge{int to,nex;}edge[N << 1];

void Add(int u,int v){edge[++dt] = (Edge){v,head[u]};head[u] = dt;du[u]++;}

void Dfs(int u,int pre)

{

    if(str[u] == 'W')w[u] = true;

    for(int i = head[u];i;i = edge[i].nex)if(edge[i].to != pre)

    {

        Dfs(edge[i].to,u);

        if(!w[edge[i].to])du[u]--,du[edge[i].to]--;

        w[u] |= w[edge[i].to];

    }

    if(w[u])tot++;

}

void rebuild()

{

    for(int i = 1;i <= n;i++)if(str[i] == 'W')rt = i;

    Dfs(rt,-1);

    for(int i = 1;i <= n;i++)if(w[i])a[i] = (str[i] == 'B') ^ (du[i] & 1),p += !a[i];

}

int dp[N][2],f[N];

void dfs(int u,int pre)

{

    f[u] = (tot - 1) * 2 + p;

    dp[u][0] = a[u] ? -1 : 1;

    for(int i = head[u];i;i = edge[i].nex)if(edge[i].to != pre && w[edge[i].to])

    {

        dfs(edge[i].to,u);

        f[u] = min(f[u],f[edge[i].to]);

        f[u] = min(f[u],(tot - 1) * 2 + p - dp[u][0] - dp[edge[i].to][1] - 1);

        f[u] = min(f[u],(tot - 1) * 2 + p - dp[u][1] - dp[edge[i].to][0] - 1);

        dp[u][0] = max(dp[u][0],dp[edge[i].to][0] + 1 + (a[u] ? -1 : 1));

        dp[u][1] = max(dp[u][1],dp[edge[i].to][1] + 1 + (a[u] ? -1 : 1));

    }

}

int main()

{

    

    scanf("%d",&n);int x,y;

    for(int i = 1;i < n;i++)scanf("%d %d",&x,&y),Add(x,y),Add(y,x);

    scanf("%s",str + 1);rebuild();dfs(rt,-1);

    printf("%d\n",!tot ? tot : f[rt]);

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

const int MAXN=100100;

vector<int> arr[MAXN];

char ch[MAXN];

int col[MAXN],deg[MAXN],val[MAXN],can[MAXN];

int f[MAXN],g[MAXN];

int n,root,sum,rest;

inline void dfs(register int now,register int pre)

{

	can[now]=col[now];

	for(register int i=0;i<(int)arr[now].size();i++)

		if(arr[now][i]!=pre)

		{

			dfs(arr[now][i],now);

			can[now]&=can[arr[now][i]];

			if(!can[arr[now][i]]) deg[now]++,deg[arr[now][i]]++;

		}

	return;

}

inline void solve(register int now,register int pre)

{

//	cout<<now<<" "<<pre<<endl;

	sum+=deg[now];

	if((deg[now]+col[now])&1) val[now]=0;

	else val[now]=2,sum++;

	register int fmax=0,gmax=0,flag=0;

	for(register int i=0;i<(int)arr[now].size();i++)

		if(arr[now][i]!=pre&&!can[arr[now][i]])

		{

			flag=1,solve(arr[now][i],now);

			rest=max(rest,max(f[arr[now][i]]+gmax,g[arr[now][i]]+fmax)+val[now]);

			fmax=max(fmax,f[arr[now][i]]),gmax=max(gmax,g[arr[now][i]]);

		}

	f[now]=fmax+val[now];

	if(flag) g[now]=gmax+val[now];

	else g[now]=-INT_MAX;

	return;

}

int main()

{

	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

	cin>>n;

	for(register int i=1,x,y;i<n;i++) cin>>x>>y,arr[x].push_back(y),arr[y].push_back(x);

	cin>>(ch+1);

	for(register int i=1;i<=n;i++)

	{

		col[i]=((ch[i]=='W')?0:1);

		if(!col[i]) root=i;

	}

	dfs(root,0);

	solve(root,0);

	cout<<(root?sum-rest:0)<<endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 3.5638110120777853x):
# include <iostream>

# include <cstdio>

using namespace std;

const int N = 2e5 + 12;

const int inf = 0x3f3f3f3f;

int n,head[N],dt,du[N],bac[N],que[N],rt,a[N],tot,p;char str[N];bool w[N];

struct Edge{int to,nex;}edge[N << 1];

void Add(int u,int v){edge[++dt] = (Edge){v,head[u]};head[u] = dt;du[u]++;}

void Dfs(int u,int pre)

{

    if(str[u] == 'W')w[u] = true;

    for(int i = head[u];i;i = edge[i].nex)if(edge[i].to != pre)

    {

        Dfs(edge[i].to,u);

        if(!w[edge[i].to])du[u]--,du[edge[i].to]--;

        w[u] |= w[edge[i].to];

    }

    if(w[u])tot++;

}

void rebuild()

{

    for(int i = 1;i <= n;i++)if(str[i] == 'W')rt = i;

    Dfs(rt,-1);

    for(int i = 1;i <= n;i++)if(w[i])a[i] = (str[i] == 'B') ^ (du[i] & 1),p += !a[i];

}

int dp[N][2],f[N];

void dfs(int u,int pre)

{

    f[u] = (tot - 1) * 2 + p;

    dp[u][0] = a[u] ? -1 : 1;

    for(int i = head[u];i;i = edge[i].nex)if(edge[i].to != pre && w[edge[i].to])

    {

        dfs(edge[i].to,u);

        f[u] = min(f[u],f[edge[i].to]);

        f[u] = min(f[u],(tot - 1) * 2 + p - dp[u][0] - dp[edge[i].to][1] - 1);

        f[u] = min(f[u],(tot - 1) * 2 + p - dp[u][1] - dp[edge[i].to][0] - 1);

        dp[u][0] = max(dp[u][0],dp[edge[i].to][0] + 1 + (a[u] ? -1 : 1));

        dp[u][1] = max(dp[u][1],dp[edge[i].to][1] + 1 + (a[u] ? -1 : 1));

    }

}

int main()

{

    

    scanf("%d",&n);int x,y;

    for(int i = 1;i < n;i++)scanf("%d %d",&x,&y),Add(x,y),Add(y,x);

    scanf("%s",str + 1);rebuild();dfs(rt,-1);

    printf("%d\n",!tot ? tot : f[rt]);

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define N 100005



using namespace std;



inline int input() {

	int x; char ch; while (!isdigit(ch = getchar()));

	for (x = ch ^ 48; isdigit(ch = getchar()); x = x * 10 + (ch ^ 48));

	return x;

}



template <class T> void chkmax(T &x, T y) { x = x > y ? x : y; }

template <class T> void chkmin(T &x, T y) { x = x < y ? x : y; }



int n;

int du[N], dp[N];

int val[N], res, cnt, tot;

bool c[N], del[N];

vector<int> G[N];

char s[N];



inline void AddEdge(int x, int y) {

	G[x].push_back(y), ++du[x];

	G[y].push_back(x), ++du[y];

}



void dfs(int u, int fa) {

	dp[u] = val[u];

	for (int v : G[u])

		if (v != fa && !del[v]) {

			dfs(v, u);

			chkmax(res, dp[u] + dp[v]);

			chkmax(dp[u], dp[v] + val[u]);

		}

}



int main() {

	n = input();

	for (int i = 1, u, v; i < n; ++i) {

		u = input(), v = input();

		AddEdge(u, v);

	}

	scanf("%s", s + 1);

	for (int i = 1; i <= n; ++i)

		c[i] = s[i] == 'B';

		

	queue<int> que;

	for (int i = 1; i <= n; ++i)

		if (c[i] && du[i] == 1) que.push(i);

	while (!que.empty()) {

		int u = que.front(); que.pop();

		del[u] = true, ++tot;

		for (int v : G[u])

			if ((--du[v]) == 1 && c[v]) que.push(v);

	}

	

	if (tot == n) return puts("0"), 0;



	for (int u = 1; u <= n; ++u) {

		if (del[u]) continue;

		if (c[u] ^ (du[u] & 1)) val[u] = 0;

		else val[u] = 2, ++cnt;

	}



	for (int i = 1; i <= n; ++i)

		if (!del[i]) {

			dfs(i, 0);

			break;

		}

	printf("%d\n", (n - tot) * 2 - 2 + cnt - res);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 3.5304161345474006x):
# include <iostream>

# include <cstdio>

using namespace std;

const int N = 2e5 + 12;

const int inf = 0x3f3f3f3f;

int n,head[N],dt,du[N],bac[N],que[N],rt,a[N],tot,p;char str[N];bool w[N];

struct Edge{int to,nex;}edge[N << 1];

void Add(int u,int v){edge[++dt] = (Edge){v,head[u]};head[u] = dt;du[u]++;}

void Dfs(int u,int pre)

{

    if(str[u] == 'W')w[u] = true;

    for(int i = head[u];i;i = edge[i].nex)if(edge[i].to != pre)

    {

        Dfs(edge[i].to,u);

        if(!w[edge[i].to])du[u]--,du[edge[i].to]--;

        w[u] |= w[edge[i].to];

    }

    if(w[u])tot++;

}

void rebuild()

{

    for(int i = 1;i <= n;i++)if(str[i] == 'W')rt = i;

    Dfs(rt,-1);

    for(int i = 1;i <= n;i++)if(w[i])a[i] = (str[i] == 'B') ^ (du[i] & 1),p += !a[i];

}

int dp[N][2],f[N];

void dfs(int u,int pre)

{

    f[u] = (tot - 1) * 2 + p;

    dp[u][0] = a[u] ? -1 : 1;

    for(int i = head[u];i;i = edge[i].nex)if(edge[i].to != pre && w[edge[i].to])

    {

        dfs(edge[i].to,u);

        f[u] = min(f[u],f[edge[i].to]);

        f[u] = min(f[u],(tot - 1) * 2 + p - dp[u][0] - dp[edge[i].to][1] - 1);

        f[u] = min(f[u],(tot - 1) * 2 + p - dp[u][1] - dp[edge[i].to][0] - 1);

        dp[u][0] = max(dp[u][0],dp[edge[i].to][0] + 1 + (a[u] ? -1 : 1));

        dp[u][1] = max(dp[u][1],dp[edge[i].to][1] + 1 + (a[u] ? -1 : 1));

    }

}

int main()

{

    

    scanf("%d",&n);int x,y;

    for(int i = 1;i < n;i++)scanf("%d %d",&x,&y),Add(x,y),Add(y,x);

    scanf("%s",str + 1);rebuild();dfs(rt,-1);

    printf("%d\n",!tot ? tot : f[rt]);

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> pii;

#define x first

#define y second

#define mp make_pair

#define pb push_back

template <typename TYPE> inline void chkmax(TYPE &x,TYPE y){x<y?x=y:TYPE();}

template <typename TYPE> inline void chkmin(TYPE &x,TYPE y){y<x?x=y:TYPE();}

template <typename TYPE> void readint(TYPE &x)

{

    x=0;int f=1;char c;

    for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-1;

    for(;isdigit(c);c=getchar())x=x*10+c-'0';

    x*=f;

}

const int MAXN=100005;



int n,rt;

vector<int> G[MAXN];

char a[MAXN];

int q[MAXN],deg[MAXN];

int b[MAXN],f[MAXN],ans;

bool vis[MAXN];

void dfs(int u,int pa)

{

	int fir=0,sec=0;

	for(auto v:G[u])

	{

		if(v==pa || vis[v])continue;

		dfs(v,u);

		if(f[v]>fir)sec=fir,fir=f[v];

		else if(f[v]>sec)sec=f[v];

	}

	f[u]=b[u]+fir;

	chkmax(ans,fir+sec+b[u]);

}



int main()

{

	int x,y;

	readint(n);

	for(int i=1;i<n;++i)readint(x),readint(y),G[x].pb(y),G[y].pb(x),++deg[x],++deg[y];

	scanf("%s",a+1);

	int front=1,rear=0;

	for(int i=1;i<=n;++i)if(deg[i]==1 && a[i]=='B')q[++rear]=i,vis[i]=1;

	while(front<=rear)

	{

		x=q[front++];

		for(auto y:G[x])

		{

			if(vis[y])continue;

			--deg[y];

			if(deg[y]==1 && a[y]=='B')q[++rear]=y,vis[y]=1;

		}

	}

	if(rear==n)return 0*printf("0\n");

	int sum=-2;

	for(int i=1;i<=n;++i)

		if(!vis[i])

		{

			b[i]=(a[i]=='W')^(deg[i]&1);

			sum+=2+b[i];

			if(!rt)rt=i;

		}

	dfs(rt,-1);

	printf("%d\n",abs(sum-ans*2)); 

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 3.519356592079163x):
#include <bits/stdc++.h>

using namespace std;



const int N = 1e5 + 100;



int n, ind[N], dp[N];

int sum, mn;

bool vis[N];

char s[N];



struct edg {

  int v;

  edg *nxt;

} pol[N << 1], *h[N], *cur = pol;



void add(int u, int v) {

  edg *p = ++cur, *q = ++cur;

  ind[u]++, ind[v]++;

  p->v = v, p->nxt = h[u], h[u] = p;

  q->v = u, q->nxt = h[v], h[v] = q;

}



void topo() {

  queue <int> Q;

  for (int i = 1; i <= n; i++) {

    if (s[i] == 'B' && ind[i] == 1) {

      Q.push(i);

    }

  }

  while (!Q.empty()) {

    int u = Q.front();

    Q.pop();

    vis[u] = 1;

    for (edg *p = h[u]; p; p = p->nxt) {

      int v = p->v;

      if (ind[v]) ind[v]--;

      if (s[v] == 'B' && ind[v] == 1 && vis[v] == 0) {

        Q.push(v);

      }

    }

  }

}



int tp(int u) {

  return (ind[u] & 1) ^ (s[u] == 'W');

}



int val(int u) {

  return tp(u) == 1 ? -2 : 0;

}



void dfs(int u, int fa) {

  sum += (tp(u) == 1) + 2;

  dp[u] = val(u);

  for (edg *p = h[u]; p; p = p->nxt) {

    int v = p->v;

    if (v == fa || vis[v]) continue ;

    dfs(v, u);

    mn = min(mn, dp[u] + dp[v]);

    dp[u] = min(dp[u], dp[v] + val(u));

  }

}



int main() {

  scanf("%d", &n);

  for (int i = 1; i < n; i++) {

    int u, v;

    scanf("%d %d", &u, &v);

    add(u, v);

  }

  scanf("%s", s + 1);

  topo();

  int x = 1;

  while (x <= n) {

    if (vis[x] == 0) break ;

    x++;

  }

  dfs(x, 0);

  sum -= 2;

  printf("%d\n", sum + mn);

  return 0;

}