stablegradients/pie-gem5-pairs huggingface dataset:
// 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.5534007332881425x):
#include <bits/stdc++.h>

using namespace std;

#define N 100010

int ea[N*2],eb[N*2],ec[N],tot,n;

void add(int x,int y){

	tot++;ea[tot]=y;eb[tot]=ec[x];ec[x]=tot;

}

int d[N],q[N],f[N],sum,minx;

bool die[N];

char s[N];

int read(){

	int x=0,f=1;

	char ch=getchar();

	while (ch<'0' || ch>'9'){

		if (ch=='-') f=-1;

		ch=getchar();

	}

	while (ch>='0' && ch<='9'){

		x=x*10+ch-'0';ch=getchar();

	}

	return x*f;

}

void topsort(){

	int t=1,w=0;

	for (int i=1;i<=n;++i) if (s[i]=='B' && d[i]==1) q[++w]=i;

	while (t<=w){

		int x=q[t++];die[x]=1;

		for (int i=ec[x];i;i=eb[i]){

			if (d[ea[i]]) d[ea[i]]--;

			if (s[ea[i]]=='B' && d[ea[i]]==1 && !die[ea[i]]) q[++w]=ea[i];

		}

	}

}

int check(int x){

	return (d[x]&1)^(s[x]=='W'); 

}

int val(int x){

	if (check(x)==1) return -2;

	else return 0;

}

void dfs(int fa,int x){

	sum+=(check(x)==1)+2;

	f[x]=val(x);

	for (int i=ec[x];i;i=eb[i]){

		if (ea[i]!=fa && !die[ea[i]]){

			dfs(x,ea[i]);

			minx=min(minx,f[x]+f[ea[i]]);

			f[x]=min(f[x],f[ea[i]]+val(x));

		}

	}

}

signed main(){

	n=read();

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

		int x=read(),y=read();

		add(x,y);add(y,x);d[x]++;d[y]++;

	}

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

	topsort();int x;

	for (x=1;x<=n;++x) if (!die[x]) break;

	if (x>n) puts("0");

	else{

		dfs(0,x);sum-=2;cout<<sum+minx<<endl;

	}

	return 0;

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

using namespace std;

const int M=1e5+5;

vector<int>mmp[M];

int col[M],du[M],val[M],dp1[M],dp2[M],n,rt,tot,more;

bool allb[M];

char ch[M];

void in()

{

    int a,b;

    scanf("%d",&n);

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

    scanf("%d%d",&a,&b),mmp[a].push_back(b),mmp[b].push_back(a);

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

    for(int i=1;i<=n;++i)col[i]=ch[i]=='W'?0:1,rt=col[i]?rt:i;

}

void dfs(int v,int f)

{

    allb[v]=col[v];int to;

    for(int i=mmp[v].size()-1;i>=0;--i)

    {

        to=mmp[v][i];if(to==f)continue;

        dfs(to,v);

        if(!allb[to])++du[v],++du[to];

        allb[v]&=allb[to];

    }

}

void dp(int v,int f)

{

    tot+=du[v];

    if((du[v]+col[v])&1)val[v]=0;

    else val[v]=2,++tot;

    int mx1=0,mx2=0,to;bool flag=0;

    for(int i=mmp[v].size()-1;i>=0;--i)

    {

        to=mmp[v][i];if(to==f||allb[to])continue;

        flag=1;dp(to,v);

        more=max(more,max(dp1[to]+mx2+val[v],dp2[to]+mx1+val[v]));

        mx1=max(dp1[to],mx1);mx2=max(dp2[to],mx2);

    }

    dp1[v]=mx1+val[v];dp2[v]=flag?mx2+val[v]:-INT_MAX;

}

void ac()

{

    dfs(rt,0);dp(rt,0);

    if(rt)printf("%d",tot-more);

    else printf("0");

}

int main()

{

    in();ac();

    return 0;

}

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

using namespace std;

#define maxn 100005

#define INF 99999999

int n, root, Ans, ans, C[maxn], mark[maxn];

int degree[maxn], dp1[maxn], dp2[maxn];

int val[maxn];



int read()

{

	int x = 0, k = 1;

	char c; c = getchar();

	while(c < '0' || c > '9') { if(c == '-') k = -1; c = getchar(); }

	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

	return x * k;

}



struct edge

{

    int cnp, to[maxn * 2], last[maxn * 2], head[maxn];

    edge() { cnp = 1; }

    void add(int u, int v)

    {

        to[cnp] = v, last[cnp] = head[u], head[u] = cnp ++;

        to[cnp] = u, last[cnp] = head[v], head[v] = cnp ++;

    }

}E1;



void dfs(int u, int fa)

{

	mark[u] = C[u];

	for(int i = E1.head[u]; i; i = E1.last[i])

	{

		int v = E1.to[i];

		if(v == fa) continue;

		dfs(v, u);

		if(!mark[v]) ++ degree[u], ++ degree[v];

		mark[u] &= mark[v];

	}

}



void dfs2(int u, int fa)

{

	int mx1 = 0, mx2 = 0; bool flag = 0;

	Ans += degree[u];

	if((degree[u] + C[u]) & 1) val[u] = 0;

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

	for(int i = E1.head[u]; i; i = E1.last[i])

	{

		int v = E1.to[i];

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

		flag = 1; dfs2(v, u);

		ans = max(ans, max(dp1[v] + mx2 + val[u], dp2[v] + mx1 + val[u]));

		mx1 = max(dp1[v], mx1), mx2 = max(dp2[v], mx2);

	}

	dp1[u] = mx1 + val[u], dp2[u] = flag ? mx2 + val[u] : -INF;

}



int main()

{

	n = read();

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

	{

		int x = read(), y = read();

		E1.add(x, y);

	}

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

	{

		char c; cin >> c;

		if(c == 'B') C[i] = 1;

		else root = i; 

	}

	if(!root) { puts("0"); return 0; }

	dfs(root, 0); dfs2(root, 0);

	printf("%d\n", Ans - ans);

	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'))==-1) return puts("0"),0; DFS(r,0), Cal(r,0), Dia(f=r,0,m=c[r]<<1), Dia(r=f,0,m=c[f]<<1), printf("%d\n",Ans-m+((c[r]&&c[f])<<1)); return 0;

}

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

using namespace std;

#define N 105000

int n,head[N],cnt,is[N],f[N],g[N],dp[N][2],st,as=1e9,a,b;

char s[N];

struct edge{int t,next;}ed[N*2];

void adde(int f,int t){ed[++cnt]=(edge){t,head[f]};head[f]=cnt;ed[++cnt]=(edge){f,head[t]};head[t]=cnt;}

void dfs(int u,int fa){is[u]=s[u]=='W';for(int i=head[u];i;i=ed[i].next)if(ed[i].t!=fa)dfs(ed[i].t,u),is[u]|=is[ed[i].t];}

void dfs1(int u,int fa){int is1=(fa?0:1);for(int i=head[u];i;i=ed[i].next)if(ed[i].t!=fa&&is[ed[i].t])dfs1(ed[i].t,u),f[u]+=f[ed[i].t]+2,is1++;if((is1&1)^(s[u]=='B'))f[u]++;}

void dfs2(int u,int fa){for(int i=head[u];i;i=ed[i].next)if(ed[i].t!=fa&&is[ed[i].t])g[ed[i].t]=g[u]+f[u]-f[ed[i].t],dfs2(ed[i].t,u);}

void dfs3(int u,int fa)

{

	int su=0,m1=1e9,m2=1e9,m3=1e9,is1=fa?0:1;

	for(int i=head[u];i;i=ed[i].next)

	if(ed[i].t!=fa&&is[ed[i].t])

	{

		is1++;

		dfs3(ed[i].t,u);

		su+=f[ed[i].t]+2;

		if(m1>dp[ed[i].t][0]-f[ed[i].t]-1)m1=dp[ed[i].t][0]-f[ed[i].t]-1;

		if(m2>dp[ed[i].t][1]-f[ed[i].t]-1)m3=m2,m2=dp[ed[i].t][1]-f[ed[i].t]-1;

		else if(m3>dp[ed[i].t][1]-f[ed[i].t]-1)m3=dp[ed[i].t][1]-f[ed[i].t]-1;

	}

	dp[u][0]=(m1>0?0:m1)+f[u]+((is1&1)^(s[u]=='B')?-1:1);

	dp[u][1]=m2+f[u]+((is1&1)^(s[u]=='B')?-1:1);

	if(dp[u][1]>f[u])dp[u][1]=f[u];

	if(m2>0)m3=m2,m2=0;else if(m3>0)m3=0;

	for(int i=head[u];i;i=ed[i].next)

	if(ed[i].t!=fa&&is[ed[i].t])

	{

		int s1=dp[ed[i].t][0]-f[ed[i].t]-1;

		if(dp[ed[i].t][1]-f[ed[i].t]-1==m2)s1+=m3;

		else s1+=m2;

		int as1=f[u]+g[u]+s1+((is1&1)^(s[u]=='B')?-1:1);

		if(m3==0&&((is1&1)^(s[u]=='B'))==0)as1--;

		if(as>as1)as=as1;

	}

	for(int i=head[u];i;i=ed[i].next)

	if(ed[i].t!=fa&&is[ed[i].t])

	{

		int s1=dp[ed[i].t][1]-f[ed[i].t]-1;

		int as1=f[u]+g[u]+s1+((is1&1)^(s[u]=='B')?-1:1);

		if(as>as1)as=as1;

	}

}

int main()

{

	scanf("%d",&n);

	for(int i=1;i<n;i++)scanf("%d%d",&a,&b),adde(a,b);

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

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

	dfs(st,0);dfs1(st,0);as=f[st];dfs2(st,0);dfs3(st,0);

	if(!st)as=0;printf("%d\n",as);

}
// 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'))==-1) return puts("0"),0; DFS(r,0), Cal(r,0), Dia(f=r,0,m=c[r]<<1), Dia(r=f,0,m=c[f]<<1), printf("%d\n",Ans-m+((c[r]&&c[f])<<1)); return 0;

}

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

#include<algorithm>

using namespace std;

int n,tot,sum,a[2100000],f[2100000],deg[2100000],dp[2100000][2];

bool w[2100000]; char s[2100000];

int edgenum,vet[4100000],Next[4100000],Head[2100000];

void addedge(int u,int v){

    vet[++edgenum]=v; deg[v]^=1;

    Next[edgenum]=Head[u];

	Head[u]=edgenum;

}

void dfs(int u,int fa){

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

	for (int e=Head[u];e;e=Next[e])

		if (vet[e]!=fa){

			dfs(vet[e],u);

			if (!w[vet[e]]){

				deg[u]^=1;

				deg[vet[e]]^=1;

			}

			w[u]|=w[vet[e]];

		}

	if (w[u]) tot++;

}

void dfs2(int u,int fa){

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

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

	for (int e=Head[u];e;e=Next[e])

		if (vet[e]!=fa&&w[vet[e]]){

	        dfs2(vet[e],u);

	        f[u]=min(f[u],f[vet[e]]);

	        f[u]=min(f[u],(tot-1)*2+sum-dp[u][0]-dp[vet[e]][1]-1);

	        f[u]=min(f[u],(tot-1)*2+sum-dp[u][1]-dp[vet[e]][0]-1);

	        dp[u][0]=max(dp[u][0],dp[vet[e]][0]+1+(a[u]?-1:1));

	        dp[u][1]=max(dp[u][1],dp[vet[e]][1]+1+(a[u]?-1:1));

	    }

}

int main(){

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

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

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

		addedge(u,v); addedge(v,u);

	}

	scanf("%s",s+1); int rt=0;

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

		if (s[i]=='W') rt=i;

	if (!rt){

		puts("0");

		return 0;

	}

	dfs(rt,0);

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

		if (w[i]){

			a[i]=(s[i]=='B')^deg[i];

			sum+=!a[i];//翻转后的颜色 

		}

	dfs2(rt,0);

	printf("%d\n",f[rt]);

	return 0;

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

using namespace std;

const int N = 100005;

int n,s,u,md,f[N];

char c[N];

vector<int> e[N];

int dfs(int x,int fa)

{

	int ret = (c[x] == 'W');int deg = fa > 0;

	for(int i = 0;i < e[x].size();i ++)

	{

		int y = e[x][i];

		if(y != fa && dfs(y,x))

			ret = 1,s += 2,deg ++;

	}

	if(ret)

	{

		f[x] = (deg&1) != (c[x] == 'W');

		s += f[x];f[x] *= 2;

	}

	else

		f[x] = -1;

	return ret;

}

void dfs2(int x,int fa,int d)

{

	d += f[x];if(d >= md) md = d,u = x;

	for(int i = 0;i < e[x].size();i ++)

	{

		if(e[x][i] != fa && f[e[x][i]] != -1)

			dfs2(e[x][i],x,d);

	}

}

int main()

{

	scanf("%d",&n);

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

	{

		int x,y;

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

		e[x].push_back(y);

		e[y].push_back(x);

	}

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

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

		if(c[i] == 'W')

		{

			dfs(i,0);md = -N;

			dfs2(i,0,0);md = -N;

			dfs2(u,0,0);

			printf("%d\n",s > 1?s-md:1);

			return 0;

		}

	printf("0\n");

	return 0;

}

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

#include<algorithm>

using namespace std;

int n,tot,sum,a[2100000],f[2100000],deg[2100000],dp[2100000][2];

bool w[2100000]; char s[2100000];

int edgenum,vet[4100000],Next[4100000],Head[2100000];

void addedge(int u,int v){

    vet[++edgenum]=v; deg[v]^=1;

    Next[edgenum]=Head[u];

	Head[u]=edgenum;

}

void dfs(int u,int fa){

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

	for (int e=Head[u];e;e=Next[e])

		if (vet[e]!=fa){

			dfs(vet[e],u);

			if (!w[vet[e]]){

				deg[u]^=1;

				deg[vet[e]]^=1;

			}

			w[u]|=w[vet[e]];

		}

	if (w[u]) tot++;

}

void dfs2(int u,int fa){

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

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

	for (int e=Head[u];e;e=Next[e])

		if (vet[e]!=fa&&w[vet[e]]){

	        dfs2(vet[e],u);

	        f[u]=min(f[u],f[vet[e]]);

	        f[u]=min(f[u],(tot-1)*2+sum-dp[u][0]-dp[vet[e]][1]-1);

	        f[u]=min(f[u],(tot-1)*2+sum-dp[u][1]-dp[vet[e]][0]-1);

	        dp[u][0]=max(dp[u][0],dp[vet[e]][0]+1+(a[u]?-1:1));

	        dp[u][1]=max(dp[u][1],dp[vet[e]][1]+1+(a[u]?-1:1));

	    }

}

int main(){

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

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

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

		addedge(u,v); addedge(v,u);

	}

	scanf("%s",s+1); int rt=0;

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

		if (s[i]=='W') rt=i;

	if (!rt){

		puts("0");

		return 0;

	}

	dfs(rt,0);

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

		if (w[i]){

			a[i]=(s[i]=='B')^deg[i];

			sum+=!a[i];//翻转后的颜色 

		}

	dfs2(rt,0);

	printf("%d\n",f[rt]);

	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'))==-1) return puts("0"),0; DFS(r,0), Cal(r,0), Dia(f=r,0,m=c[r]<<1), Dia(r=f,0,m=c[f]<<1), printf("%d\n",Ans-m+((c[r]&&c[f])<<1)); return 0;

}

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

#include <cstdio>

#include <queue>

#include <cstring>

#include <algorithm>

#define int long long

using namespace std;

const int N = 1e5 + 5;

int read() {

	int x = 0, f = 1; char ch;

	while(! isdigit(ch = getchar())) (ch == '-') && (f = -f);

	for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 3) + (x << 1) + (ch ^ 48));

	return x * f;

}

template <class T> T Max(T a, T b) { return a > b ? a : b; }

template <class T> T Min(T a, T b) { return a < b ? a : b; }

struct Edge {

	int to;

	Edge *nxt;

	Edge(int to, Edge *nxt) : to(to), nxt(nxt) {}

} *head[N];

void add(int x, int y) {head[x] = new Edge(y, head[x]);}

char s[N];

queue <int> q;

int n, mn, sum, f[N], deg[N], del[N];

void topsort() {

	for(int i = 1; i <= n; ++ i) if(deg[i] == 1 && s[i] == 'B') q.push(i);

	while(! q.empty()) {

		int x = q.front(); q.pop();

		del[x] = 1;

		for(Edge *i = head[x]; i; i = i->nxt) {

			deg[i->to] --;

			if(s[i->to] == 'B' && deg[i->to] == 1 && del[i->to] == 0) q.push(i->to);

		}

	}

}

int v(int x) {return (deg[x] & 1) ^ (s[x] == 'W');}

int val(int x) {return (v(x) == 1) ? -2 : 0;}

void dfs(int x, int fa) {

	sum += (v(x) == 1) + 2; f[x] = val(x);

	for(Edge *i = head[x]; i; i= i->nxt) {

		if(i->to == fa || del[i->to]) continue;

		dfs(i->to, x);

		mn = min(mn, f[x] + f[i->to]);

		f[x] = min(f[x], f[i->to] + val(x));

	}

}

signed main() {

	n = read();

	for(int i = 1, x, y; i < n; ++ i) deg[x = read()] ++, deg[y = read()] ++, add(x, y), add(y, x);

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

	int x; for(x = 1; x <= n; ++ x) if(del[x] == 0) break;

	if(x > n) return puts("0"), 0;

	dfs(x, 0); sum -= 2; printf("%d\n", sum + mn);

	return 0;

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

using namespace std;

const int N = 100005;

int n,s,u,md,f[N];

char c[N];

vector<int> e[N];

int dfs(int x,int fa)

{

	int ret = (c[x] == 'W');int deg = fa > 0;

	for(int i = 0;i < e[x].size();i ++)

	{

		int y = e[x][i];

		if(y != fa && dfs(y,x))

			ret = 1,s += 2,deg ++;

	}

	if(ret)

	{

		f[x] = (deg&1) != (c[x] == 'W');

		s += f[x];f[x] *= 2;

	}

	else

		f[x] = -1;

	return ret;

}

void dfs2(int x,int fa,int d)

{

	d += f[x];if(d >= md) md = d,u = x;

	for(int i = 0;i < e[x].size();i ++)

	{

		if(e[x][i] != fa && f[e[x][i]] != -1)

			dfs2(e[x][i],x,d);

	}

}

int main()

{

	scanf("%d",&n);

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

	{

		int x,y;

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

		e[x].push_back(y);

		e[y].push_back(x);

	}

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

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

		if(c[i] == 'W')

		{

			dfs(i,0);md = -N;

			dfs2(i,0,0);md = -N;

			dfs2(u,0,0);

			printf("%d\n",s > 1?s-md:1);

			return 0;

		}

	printf("0\n");

	return 0;

}

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

#include <cstdio>

#include <queue>

#include <cstring>

#include <algorithm>

#define int long long

using namespace std;

const int N = 1e5 + 5;

int read() {

	int x = 0, f = 1; char ch;

	while(! isdigit(ch = getchar())) (ch == '-') && (f = -f);

	for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 3) + (x << 1) + (ch ^ 48));

	return x * f;

}

template <class T> T Max(T a, T b) { return a > b ? a : b; }

template <class T> T Min(T a, T b) { return a < b ? a : b; }

struct Edge {

	int to;

	Edge *nxt;

	Edge(int to, Edge *nxt) : to(to), nxt(nxt) {}

} *head[N];

void add(int x, int y) {head[x] = new Edge(y, head[x]);}

char s[N];

queue <int> q;

int n, mn, sum, f[N], deg[N], del[N];

void topsort() {

	for(int i = 1; i <= n; ++ i) if(deg[i] == 1 && s[i] == 'B') q.push(i);

	while(! q.empty()) {

		int x = q.front(); q.pop();

		del[x] = 1;

		for(Edge *i = head[x]; i; i = i->nxt) {

			deg[i->to] --;

			if(s[i->to] == 'B' && deg[i->to] == 1 && del[i->to] == 0) q.push(i->to);

		}

	}

}

int v(int x) {return (deg[x] & 1) ^ (s[x] == 'W');}

int val(int x) {return (v(x) == 1) ? -2 : 0;}

void dfs(int x, int fa) {

	sum += (v(x) == 1) + 2; f[x] = val(x);

	for(Edge *i = head[x]; i; i= i->nxt) {

		if(i->to == fa || del[i->to]) continue;

		dfs(i->to, x);

		mn = min(mn, f[x] + f[i->to]);

		f[x] = min(f[x], f[i->to] + val(x));

	}

}

signed main() {

	n = read();

	for(int i = 1, x, y; i < n; ++ i) deg[x = read()] ++, deg[y = read()] ++, add(x, y), add(y, x);

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

	int x; for(x = 1; x <= n; ++ x) if(del[x] == 0) break;

	if(x > n) return puts("0"), 0;

	dfs(x, 0); sum -= 2; printf("%d\n", sum + mn);

	return 0;

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



using namespace std;



#define PROBLEM "C"

#define TESTC ""



#define USE_CPPIO() ios_base::sync_with_stdio(0); cin.tie(0)

typedef pair<int, int> P;

#define F first

#define S second

#define INF 0x3f3f3f3f

#define MP make_pair

#define PB push_back

#define MAXN 100005

#define LL long long



LL l[MAXN];

LL r[MAXN];

LL dp[MAXN];



int main()

{

	#ifdef DBG

	freopen(PROBLEM TESTC ".in", "r", stdin);

	freopen(PROBLEM ".out", "w", stdout);

	#endif



	int n;

	while(~scanf("%d",&n))

	{

		int tmp;

		memset(dp, 0, sizeof(dp));

		memset(r,0,sizeof(r));

		memset(l,0,sizeof(l));

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

		{

			scanf("%d",&tmp);

			dp[i] = tmp;

		}

		//算前綴

		l[0] = dp[0];

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

			l[i] = __gcd(l[i-1], dp[i]);

		

		//算後綴

		r[n-1] = dp[n-1];

		for(int i = n-2; i >= 0; i--)

			r[i] = __gcd(r[i+1], dp[i]);



		LL ans = 1;

		//嘗試砍每一個

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

			ans = max(__gcd(r[i+1],l[i-1]), ans);

		

		//砍頭砍尾

		ans = max(ans, max(r[1],l[n-2]));





		cout << ans << '\n';



		

	}

	

	



	return 0;

}

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

using namespace std;



int main(int argc, char const *argv[])

{

	int nums;

	while(~scanf("%d",&nums)){

		int fr[nums],bk[nums],arr[nums];

		for (int i = 0; i < nums; ++i)

			scanf("%d",&arr[i]);

		fr[0]=arr[0];

		bk[nums-1]=arr[nums-1];

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

			fr[i]=__gcd(arr[i],fr[i-1]);

		for (int i = nums-2; i >= 0; --i)

			bk[i]=__gcd(arr[i],bk[i+1]);



		// for (int i = 0; i < nums; ++i)

		// {

		// 	printf("fr[%d]==%d\n",i,fr[i] );

		// }



		// for (int i = 0; i < nums; ++i)

		// {

		// 	printf("bk[%d]==%d\n",i,bk[i] );

		// }



		int ans=0;

		for (int i = 0; i < nums; ++i)

		{

			if (i==0)

				ans=max(ans,bk[i+1]);

			else if (i==nums-1)

				ans=max(ans,fr[i-1]);

			else{

				ans=max(ans, __gcd( bk[i+1],fr[i-1]) );

			}



		}

		printf("%d\n",ans);

	}

	return 0;

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



using namespace std;



#define PROBLEM "C"

#define TESTC ""



#define USE_CPPIO() ios_base::sync_with_stdio(0); cin.tie(0)

typedef pair<int, int> P;

#define F first

#define S second

#define INF 0x3f3f3f3f

#define MP make_pair

#define PB push_back

#define MAXN 100005

#define LL long long



LL l[MAXN];

LL r[MAXN];

LL dp[MAXN];



int main()

{

	#ifdef DBG

	freopen(PROBLEM TESTC ".in", "r", stdin);

	freopen(PROBLEM ".out", "w", stdout);

	#endif



	int n;

	while(~scanf("%d",&n))

	{

		int tmp;

		memset(dp, 0, sizeof(dp));

		memset(r,0,sizeof(r));

		memset(l,0,sizeof(l));

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

		{

			scanf("%d",&tmp);

			dp[i] = tmp;

		}

		//算前綴

		l[0] = dp[0];

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

			l[i] = __gcd(l[i-1], dp[i]);

		

		//算後綴

		r[n-1] = dp[n-1];

		for(int i = n-2; i >= 0; i--)

			r[i] = __gcd(r[i+1], dp[i]);



		LL ans = 1;

		//嘗試砍每一個

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

			ans = max(__gcd(r[i+1],l[i-1]), ans);

		

		//砍頭砍尾

		ans = max(ans, max(r[1],l[n-2]));





		cout << ans << '\n';



		

	}

	

	



	return 0;

}

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

#define forn(i, n) for (int i = 0; i<(int)n; ++i)

#define rfor(i, n) for (int i = n-1; i>=0; --i)

#define rmod(x, y) (((x%y)+y)%y)

#define pb(x) push_back(x)

using namespace std;

typedef vector<int>::iterator vit;

typedef unsigned int uint;

typedef unsigned short ushort;

typedef long long ll;

const int MAXN = 1024;



//OPERATORS





//GLOBALS





//FUNCTIONS





int main()

{

	ios::sync_with_stdio(0);

	cin.tie(0);

	int n; cin >> n;

	vector<int> fu(n);

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

		cin >> fu[i];

	}

	vector<int> desdeI(n);

	vector<int> desdeD(n);

	

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

		if(i == 0)

			desdeI[i] = fu[i];

		else{

			desdeI[i] = __gcd(fu[i],desdeI[i-1]);

		}

	}



	for(int i = n-1; i >= 0; i--){

		if(i == n-1)

			desdeD[i] = fu[i];

		else{

			desdeD[i] = __gcd(fu[i],desdeD[i+1]);

		}

	}

	int mxG = 0;

	if(1 <= n-1){

		mxG = (desdeD[1]);

	}

	if(n-2 >= 0){

		mxG = max(mxG,desdeI[n-2]);

	}

	

	for(int i = 0; i < n-2; i++){

		if(__gcd(desdeI[i],desdeD[i+2]) > mxG){

			mxG = __gcd(desdeI[i],desdeD[i+2]);

		}

	}

	cout << mxG << endl;



	return 0;

}