stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include<cstdio>

#include<cstring>

#include<algorithm>

#include<map>

#define SF scanf

#define PF printf

#define MAXN 300010

#define INF 0x3FFFFFFF

#define MOD 998244353

using namespace std;

typedef long long ll;

typedef map<ll,ll>::iterator mit;

int n,q;

ll qx[MAXN];

map<ll,ll> mp;

ll used[MAXN];

int main(){

	SF("%d%d",&n,&q);

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

		SF("%lld",&qx[i]);

	qx[0]=n;

	mp[qx[q]]++;

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

		while(mp.rbegin()->first>qx[i]){

			mit it=mp.end();

			it--;	

			mp[it->first%qx[i]]+=it->second;

			mp[qx[i]]+=it->second*(it->first/qx[i]);

			mp.erase(it);

		}

	}

	mit it=mp.begin();

	for(;it!=mp.end();it++)

		used[it->first]+=it->second;

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

		used[i]=used[i]+used[i+1];

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

		PF("%lld\n",used[i]);

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const long long MAXN=1000005;

long long n,q;

long long a[MAXN],s[MAXN],c[MAXN],ans[MAXN],tot;

int main()

{

	//freopen("seq.in","r",stdin);

	//freopen("seq.out","w",stdout);

	scanf("%lld %lld",&n,&q);

	a[tot=1]=n;

	for(long long i=1;i<=q;i++)

	{

		long long x;

		scanf("%lld",&x);

		while(tot&&a[tot]>=x)

			tot--;

		a[++tot]=x;

	}

	q=tot;

	s[q]=1;

	for(long long i=q;i>=1;i--)

	{

		long long l=a[i];

		long long p=i-1;

		while(p)

		{

			s[p]+=(l/a[p])*s[i];

			l%=a[p];

			p=lower_bound(a+1,a+p,l)-a-1;

		}

		ans[l]+=s[i];

	}

	for(long long i=n;i>=1;i--)

		ans[i]+=ans[i+1];

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

		printf("%lld\n",ans[i]);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

#define ll long long

#define res register ll

using namespace std;

ll n,num,m;

ll len[101010];

ll f[101010],sum[101010];

inline ll read()

{

  ll X=0,w=0;

  char ch=0;

  while(!isdigit(ch))

  {

    w|=ch=='-';

    ch=getchar();

  }

  while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();

  return w?-X:X;

}

void work(ll x,ll base)

{

  if (x<len[1])

  {

    sum[x]+=base;

    return;

  }

  ll l=1,r=n;

  ll total;

  while (l<=r)

  {

    ll mid=(l+r)/2;

    if (len[mid]<=x)

    {

      total=mid;

      l=mid+1;

    }

    else r=mid-1;

  }

  f[total]+=base*(x/len[total]);

  x=x%len[total];

  if (x) work(x,base);

}

int main()

{

  n=read(),m=read();

  num=1;

  len[1]=n;

  ll x;

  for (res i=1; i<=m; ++i)

  {

    x=read();

    while (x<=len[num] && num)

      --num;

    ++num;

    len[num]=x;

  }

  m=n;

  n=num;

  f[n]=1;

  for (res i=n-1; i>=1; --i)

  {

    f[i]+=f[i+1]*(len[i+1]/len[i]);

    work(len[i+1]%len[i],f[i+1]);

  }

  for (res i=len[1]; i>=1; --i)

    sum[i]+=sum[i+1];

  for (res i=1; i<=len[1]; ++i)

    sum[i]+=f[1];

  for (res i=1; i<=m; ++i)

    printf("%lld\n",sum[i]);

  return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cctype>

using namespace std;

typedef long long int64;

inline int64 read(int f = 1, int64 x = 0, char ch = ' ')

{

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

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

    return f*x;

}

const int N = 1e5+5;

int n, q, top;

int64 d[N], s[N], f[N];

void solve(int64 p, int64 q)

{

    if(!p) return;

    int r = upper_bound(s+1, s+1+top, p)-s-1;

    if(!r) d[1] += q, d[p+1] -= q;

    else f[r] += p/s[r]*q, solve(p%s[r], q);

}

int main()

{

    s[++top] = n = read(), q = read(); 

    while(q--)

    {

        int64 m = read();

        while(top&&s[top] >= m) --top;

        s[++top] = m;

    }

    f[top] = 1; 

    for(int i = top; i >= 2; --i) 

        f[i-1] += s[i]/s[i-1]*f[i], solve(s[i]%s[i-1], f[i]);

    d[1] += f[1], d[s[1]+1] -= f[1];

    for(int i = 1; i <= n; ++i) printf("%lld\n", d[i] += d[i-1]);

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

#define ll long long

using namespace std;

ll n,m,sum[200001],f[200001],cnt,q[200001];

void solve(ll x,ll y){

	if(!x)return;

	ll now=upper_bound(q+1,q+cnt+1,x)-q-1;

	if(!now)sum[1]+=y,sum[x+1]-=y;

	 else{

	 	f[now]+=x/q[now]*y;

	 	solve(x%q[now],y);

	 }

}

int main(){

	ll i,t;

	scanf("%lld%lld",&n,&m);

	cnt=1;q[1]=n;

	for(i=1;i<=m;i++){

		scanf("%lld",&t);

		while(cnt&&t<=q[cnt])cnt--;

		q[++cnt]=t;

	}

	f[cnt]=1;

	for(i=cnt;i>1;i--)f[i-1]+=q[i]/q[i-1]*f[i],solve(q[i]%q[i-1],f[i]);

	sum[1]+=f[1];sum[q[1]+1]-=f[1];

	for(i=1;i<=n;i++)printf("%lld\n",sum[i]+=sum[i-1]);

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cctype>

using namespace std;

typedef long long int64;

inline int64 read(int f = 1, int64 x = 0, char ch = ' ')

{

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

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

    return f*x;

}

const int N = 1e5+5;

int n, q, top;

int64 d[N], s[N], f[N];

void solve(int64 p, int64 q)

{

    if(!p) return;

    int r = upper_bound(s+1, s+1+top, p)-s-1;

    if(!r) d[1] += q, d[p+1] -= q;

    else f[r] += p/s[r]*q, solve(p%s[r], q);

}

int main()

{

    s[++top] = n = read(), q = read(); 

    while(q--)

    {

        int64 m = read();

        while(top&&s[top] >= m) --top;

        s[++top] = m;

    }

    f[top] = 1; 

    for(int i = top; i >= 2; --i) 

        f[i-1] += s[i]/s[i-1]*f[i], solve(s[i]%s[i-1], f[i]);

    d[1] += f[1], d[s[1]+1] -= f[1];

    for(int i = 1; i <= n; ++i) printf("%lld\n", d[i] += d[i-1]);

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 100010;

int q,n,len[N],val[N],ans[N],m;

void doit(int x,int v) {

//	printf("X %lld %lld\n", x, v);

	if (!x) return;

	int t = upper_bound(len+1,len+m+1,x) - len - 1;

//	printf("TT %lld\n", t);

	if (t == 0) ans[1] += v, ans[x+1] -= v;

	else {

		val[t] += (x / len[t]) * v;

		doit(x % len[t],v);

	}

}

signed main() {

	int x;

	scanf("%lld%lld",&n,&q);

	len[++m] = n;

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

		scanf("%lld",&x);

		while (m && len[m] >= x) -- m;

		len[++m] = x;

	}

	val[m] = 1;

	for (int i = m ; i >= 2 ; -- i) {

		val[i-1] += val[i] * (len[i] / len[i-1]);

//		printf("	%lld %lld %lld\n", len[i] % len[i - 1], val[i], i);

		doit(len[i] % len[i-1],val[i]);

	}

//	for (int i = 1; i <= m; ++i) printf("%lld\n", val[i]);

	ans[1] += val[1];

	ans[len[1]+1] -= val[1];

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

		ans[i] += ans[i-1];

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

		printf("%lld\n",ans[i]);

	return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define int long long

#define maxn (100010)

int n, m, top, s[maxn], cnt[maxn], sum[maxn];



inline int read() {

	int x = 0, f = 1;

	char ch = getchar();

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

		ch == '-' ? f = -1, ch = getchar() : ch = getchar();

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

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

	return x * f;

}



void sol(int x, int del) {

//	printf("X %lld %lld\n", x, del);

	if (!x) return;

	int pos = upper_bound(s + 1, s + top + 1, x) - s - 1; // 找到比他大的，然后-1 

//	printf("POS %lld\n", pos);

	if (!pos) sum[1] += del, sum[x + 1] -= del;

	else cnt[pos] += (x / s[pos]) * del, sol(x % s[pos], del);

}



signed main() {

	n = read(), m = read();

	s[++top] = n;

	int x;

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

		x = read();

		while (top && s[top] >= x) --top;

		s[++top] = x;

	}

	cnt[top] = 1;

	for (int i = top; i >= 2; --i) {

		cnt[i - 1] += (s[i] / s[i - 1]) * cnt[i];

//		printf("	%lld %lld %lld\n", s[i] % s[i - 1], cnt[i], i);

		sol(s[i] % s[i - 1], cnt[i]);

	}

//	for (int i = 1; i <= top; ++i) printf("%lld\n", cnt[i]);

	sum[1] += cnt[1], sum[s[1] + 1] -= cnt[1]; // s[1]为最长长度

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

	for (int i = 1; i <= n; ++i) printf("%lld\n", sum[i]); 

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <cstdio>

#include <queue>

typedef long long LL;

typedef std::pair<LL,LL> P;

std::priority_queue<P> Q;

const int N=100005;

LL a[N],cnt[N],ans[N];

void add(int i,LL x,LL y){

	cnt[i]+=x/a[i]*y;

	if (x%a[i]) Q.push(P(x%a[i],y));

}

int main(){

	int n,m,q;

	scanf("%d%d\n",&n,&q);

	a[m=1]=n;

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

		long long x;

		scanf("%lld",&x);

		for (;m && x<=a[m];m--);

		a[++m]=x;

	}

	cnt[m]=1;

	for (int i=m-1;i>=1;i--){

		for (;!Q.empty() && Q.top().first>=a[i];Q.pop()){

			P p=Q.top();

			add(i,p.first,p.second);

		}

		add(i,a[i+1],cnt[i+1]);

	}

	ans[a[1]]+=cnt[1];

	for (;!Q.empty();Q.pop())

		ans[Q.top().first]+=Q.top().second;

	for (int i=a[1];i;i--) ans[i]+=ans[i+1];

	for (int i=1;i<=n;i++) printf("%lld\n",ans[i]);

}

// Optimized solution to the same problem (faster):
#include <algorithm>

#include <cstdio>

typedef long long LL;

const int N=100005;

LL a[N],cnt[N],ans[N];

void add(int i,LL x,LL y){

	if (x<=a[1]){

		ans[x]+=y;

		return;

	}

	cnt[i]+=x/a[i]*y;x%=a[i];

	add(std::lower_bound(a+1,a+i,x)-a-1,x,y);

}

int main(){

	int n,m,q;

	scanf("%d%d\n",&n,&q);

	a[m=1]=n;

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

		long long x;

		scanf("%lld",&x);

		for (;m && x<=a[m];m--);

		a[++m]=x;

	}

	cnt[m]=1;

	for (int i=m;i>=1;i--) add(i-1,a[i],cnt[i]);

	for (int i=a[1];i;i--) ans[i]+=ans[i+1];

	for (int i=1;i<=n;i++) printf("%lld\n",ans[i]);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

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

using namespace std;

using ll = long long;



vector<ll> a(200000);



int main(void){

    ll n, k;

    cin >> n >> k;

    rep(i, n) cin >> a[i];

    ll l = 1, h = *max_element(a.begin(), a.begin() + n);

    while(l < h){

        ll mid = (l + h) / 2, cnt = 0;

        rep(i, n){

            cnt += a[i] / mid;

            if(a[i] % mid == 0) --cnt;

        }

        if(cnt <= k) h = mid;

        else l = mid + 1;

    }

    cout << h << endl;

    return 0;

}

// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

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

using namespace std;

using ll = long long;



int main(void){

    int n, k;

    cin >> n >> k;

    vector<int> a(n);

    rep(i, n) cin >> a[i];

    int l = 1, h = *max_element(a.begin(), a.end());

    while(l < h){

        int mid = (l + h) / 2, cnt = 0;

        rep(i, n){

            cnt += a[i] / mid;

            if(a[i] % mid == 0) --cnt;

        }

        if(cnt <= k) h = mid;

        else l = mid + 1;

    }

    cout << h << endl;

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



int main() {

  ios::sync_with_stdio(0);

  cin.tie(0), cout.tie(0);



  int N;

  cin >> N;



  vector<int> A(N + 1);

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

    cin >> A[i];

  }



  long long ans = 0;

  vector<int> AA = A;



  auto Eval = [&](const vector<int> &order) {

    long long cost = 0;

    A = AA;

    for (auto i : order) {

      if (i == 0) continue;

      long long cur = 0;

      for (int j = i; j <= N; j += i) {

        cur += A[j];

      }

      if (cur < 0) {

        for (int j = i; j <= N; j += i) {

          A[j] = 0;

        }

      }

    }

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

      cost += A[i];

    }

    return cost;

  };



  vector<int> order(N + 1);

  iota(begin(order), end(order), 0);

  ans = max(ans, Eval(order));

  reverse(begin(order), end(order));

  ans = max(ans, Eval(order));

  

  mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

  for (int rep = 0; rep < 10000; rep++) {

    shuffle(begin(order), end(order), rnd);

    ans = max(ans, Eval(order));

  }



  cout << ans << "\n";

  return 0;

}


// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

using namespace std;

#define ll long long

ll cap[105][105]; int par[105];

vector<int>adj[105];

const ll inf=1e12;

ll bfs(){

	memset(par, -1, sizeof(par));

	par[0]=-2;

	queue<pair<int, ll> >q;

	q.push({0, inf});

	for(;!q.empty();q.pop()){

		int nw=q.front().first; ll flow=q.front().second;

	//	cout<<nw<<" "<<flow<<" "<<par[nw]<<endl;

		for(int nx:adj[nw]) if(par[nx]==-1 && cap[nw][nx]>0){

			par[nx]=nw;

			ll nflw=min(flow, cap[nw][nx]);

		//	for(int i=1; i<=6; i++) cout<<par[i]<<" "; cout<<endl;

			if(nx==101) return nflw;

			q.push({nx, nflw});

		}

	}

	return 0;

}

ll maxflow(){

	ll flow=0, nflw;

	for(nflw=bfs();nflw;nflw=bfs()){

		flow+=nflw;

		int nw=101;

		while(nw!=0){

			int bf=par[nw];

			cap[bf][nw]-=nflw;

			cap[nw][bf]+=nflw;

			nw=bf;

		//	cout<<nw<<" "<<par[nw]<<endl;

		}

	}

	return flow;

}

void addedge(int u, int v, ll cp){

	cap[u][v]=cp;

	adj[u].push_back(v);

	adj[v].push_back(u);

}

int n, a[105];

int main(){

	scanf("%d", &n);

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

	ll optimal=0ll;

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

		if(a[i]>0){

			optimal+=a[i];

			addedge(i, 101, 1ll*a[i]);

		}else{

			addedge(0, i, -1ll*a[i]);

		}

		for(int j=2*i; j<=n; j+=i)

			addedge(i, j, inf);

	}

	/*for(int i=0; i<=101; i++) if(adj[i].size()){

		for(int j:adj[i]){

			if(cap[i][j]){

				printf("%d %d %lld\n", i, j, cap[i][j]);

			}

		}

	}*/

	ll mincut=maxflow();

	printf("%lld\n", optimal-mincut);

	return 0;

}//

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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);

}

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}


// Optimized solution to the same problem (faster):
# 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]);

}




// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
# 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]);

}




// Fastest known solution for this problem: