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

const int e[40]={0,1,1,2,2,2,3,3,3,3,4,4,4,4,4,5,5,5,5,5,

                 5,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,8,8,8,8};

int main(void)

{

  int i,x;

  long long a=0,N;

  x=scanf("%lld",&N)-1;

  while(N%2==0){x++;N/=2;}

  a+=e[x];

  for(i=3;i<=1e6;i+=2)

  {

    x=0;while(!(N%i))x++,N/=i;

    a+=e[x];

  }

  if(N>1)a++;

  return printf("%lld\n",a),0;

}

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

typedef long long LL;

const int e[40]={0,1,1,2,2,2,3,3,3,3,4,4,4,4,4,5,5,5,5,5,

                 5,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,8,8,8,8};

LL IN(void)

{

  LL x=0;short f=0,c=getchar();

  while(c<48||c>57)f^=c==45,c=getchar();

  while(c>47&&c<58)x=x*10+c-48,c=getchar();

  return f?-x:x;

}

int main(void)

{

  int x=0;LL a=0,p=7,q=11,N=IN();

  while(N%2==0){x++;N/=2;}a+=e[x],x=0;

  while(N%3==0){x++;N/=3;}a+=e[x],x=0;

  while(N%5==0){x++;N/=5;}a+=e[x];

  while(q*q<=N)

  {

    x=0;while(!(N%p)){x++;N/=p;}a+=e[x];

    x=0;while(!(N%q)){x++;N/=q;}a+=e[x];

    p+=6,q+=6;

  }

  if(N>1)a++;

  return printf("%lld\n",a),0;

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

#include<math.h>

const int e[40]={0,1,1,2,2,2,3,3,3,3,4,4,4,4,4,5,5,5,5,5,

                 5,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,8,8,8,8};

int main(void)

{

  int i,x;

  long long a=0,N;

  x=scanf("%lld",&N)-1;

  while(N%2==0){x++;N/=2;}

  a+=e[x];

  for(i=3;i<=(int)sqrt(N);i+=2)

  {

    x=0;while(!(N%i))x++,N/=i;

    a+=e[x];

  }

  if(N>1)a++;

  return printf("%lld\n",a),0;

}

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

typedef long long LL;

const int e[40]={0,1,1,2,2,2,3,3,3,3,4,4,4,4,4,5,5,5,5,5,

                 5,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,8,8,8,8};

LL IN(void)

{

  LL x=0;short f=0,c=getchar();

  while(c<48||c>57)f^=c==45,c=getchar();

  while(c>47&&c<58)x=x*10+c-48,c=getchar();

  return f?-x:x;

}

int main(void)

{

  int x=0;LL a=0,p=7,q=11,N=IN();

  while(N%2==0){x++;N/=2;}a+=e[x],x=0;

  while(N%3==0){x++;N/=3;}a+=e[x],x=0;

  while(N%5==0){x++;N/=5;}a+=e[x];

  while(q*q<=N)

  {

    x=0;while(!(N%p)){x++;N/=p;}a+=e[x];

    x=0;while(!(N%q)){x++;N/=q;}a+=e[x];

    p+=6,q+=6;

  }

  if(N>1)a++;

  return printf("%lld\n",a),0;

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

const int e[40]={0,1,1,2,2,2,3,3,3,3,4,4,4,4,4,5,5,5,5,5,

                 5,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,8,8,8,8};

int main(void)

{

  int i,x;

  long long a=0,N;

  x=scanf("%lld",&N)-1;

  while(N%2==0){x++;N/=2;}

  a+=e[x];

  for(i=3;i<=1e6;i+=2)

  {

    x=0;while(!(N%i))x++,N/=i;

    a+=e[x];

  }

  if(N>1)a++;

  return printf("%lld\n",a),0;

}

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

#include<stdlib.h>

#include<math.h>

#include<time.h>

typedef long long LL;

const int e[]={0,1,1,2,2,2,3,3,3,3,4,4,4,4,4,5,5,5,5,5,

               5,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,8,8,8,8};

const LL UnUseMethod=1e9;

LL count[2]={0};

LL IN(void)

{

  LL x=0;short f=0,c=getchar();while(c<48||c>57){f^=c==45,c=getchar();}

  while(c>47&&c<58){x=x*10+c-48,c=getchar();}return f?-x:x;

}

LL GCD(LL a,LL b){return !b?a:GCD(b,a%b);}

LL Mult(LL x,LL y,LL mod)

{LL temp=x*y-(LL)((long double)x/mod*y+1e-8)*mod;return temp<0?temp+mod:temp;}

LL BinaryModularPower(LL base,LL pow,LL mod)

{

  LL x=1;

  while(pow){if(pow&1){x=Mult(x,base,mod);}base=Mult(base,base,mod);pow>>=1;}

  return x;

}

LL f(LL x,LL mod,LL c){return (Mult(x,x,mod)+c)%x+1;}

void Exp(LL x,LL y){count[1]=0;while(!(x%y)){count[1]++;x/=y;}count[0]=x;return;}

int MillerRabin(const LL a)

{

  if(a==2)return 1;

  if(a%2==0||a==1)return 0;

  static int pr[]={2,325,9375,28178,450775,9780504,1795265022};

  int c=7;

  LL u=a-1,t=0,p=1;

  while(!(u&1)){u>>=1;t++;}

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

  {

    p=pr[i]%a;

    if(!p)return 1;

    LL x=BinaryModularPower(p,u,a);

    if(x==1)continue;

    for(int j=0;x!=a-1&&j<t;++j)

    {

      x=Mult(x,x,a);

      if(x==1)return 0;

    }

    if(x==a-1)continue;

    return 0;

  }

  return 1;

}

LL PollardRho(LL n,LL a)

{

  srand((unsigned int)time(NULL));

  LL x=rand()%n,y=x,gcd=1,k=0,i=1;

  while(gcd==1)

  {

    k++;

    x=Mult(x,x,n)+a;if(x>=n)x-=n;

    gcd=GCD(x>y?x-y:y-x,n);

    if(k==i){y=x;i<<=1;}

  }

  if(gcd==n)return PollardRho(n,a+1);

  return gcd;

}

int main(void)

{

  LL a=0,p=1,q=-1,N=IN();

  if(N<=1)return puts("0"),0;

  Exp(N,2);a=e[count[1]];N=count[0];

  Exp(N,3);a+=e[count[1]];N=count[0];

  while(q*q<=UnUseMethod)

  {

    p+=6,q+=6;

    Exp(N,p);a+=e[count[1]];N=count[0];

    Exp(N,q);a+=e[count[1]];N=count[0];

  }

  if(N<=UnUseMethod){if(N>1){a++;}return printf("%lld\n",a),0;}

  if(MillerRabin(N)){a++;return printf("%lld\n",a),0;}

  while(N>=UnUseMethod)

  {

    p=PollardRho(N,0);

    while(!MillerRabin(p))p=PollardRho(p,p);

    Exp(N,p);a+=e[count[1]];N=count[0];

  }

  if(MillerRabin(N)){a++;}return printf("%lld\n",a),0;

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

const int e[40]={0,1,1,2,2,2,3,3,3,3,4,4,4,4,4,5,5,5,5,5,

                 5,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,8,8,8,8};

int main(void)

{

  int i,x;

  long long a=0,N;

  x=scanf("%lld",&N)-1;

  while(N%2==0){x++;N/=2;}

  a+=e[x];

  for(i=3;i<=1e6;i+=2)

  {

    x=0;while(!(N%i))x++,N/=i;

    a+=e[x];

  }

  if(N>1)a++;

  return printf("%lld\n",a),0;

}

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

#include<stdlib.h>

#include<time.h>

typedef long long LL;

const int e[40]={0,1,1,2,2,2,3,3,3,3,4,4,4,4,4,5,5,5,5,5,

               5,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,8,8,8,8};

const LL UnUseMethod=10e10;

LL count[2]={0};

LL IN(void)

{

  LL x=0;short f=0,c=getchar();while(c<48||c>57){f^=c==45,c=getchar();}

  while(c>47&&c<58){x=x*10+c-48,c=getchar();}return f?-x:x;

}

LL GCD(LL a,LL b){return !b?a:GCD(b,a%b);}

LL Mult(LL x,LL y,LL mod)

{LL temp=x*y-(LL)((long double)x/mod*y+1e-8)*mod;return temp<0?temp+mod:temp;}

LL BinaryModularPower(LL base,LL pow,LL mod)

{

  LL x=1;

  while(pow){if(pow&1){x=Mult(x,base,mod);}base=Mult(base,base,mod);pow>>=1;}

  return x;

}

LL f(LL x,LL mod,LL c){return (Mult(x,x,mod)+c)%x+1;}

void Exp(LL x,LL y){count[1]=0;while(!(x%y)){count[1]++;x/=y;}count[0]=x;return;}

int MillerRabin(const LL a)

{

  if(a==2)return 1;

  if(a%2==0||a==1)return 0;

  static int pr[7]={2,325,9375,28178,450775,9780504,1795265022};

  LL u=a-1,t=0,p=1;

  while(!(u&1)){u>>=1;t++;}

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

  {

    p=pr[i]%a;

    if(!p)return 1;

    LL x=BinaryModularPower(p,u,a);

    if(x==1)continue;

    for(int j=0;x!=a-1&&j<t;++j)

    {

      x=Mult(x,x,a);

      if(x==1)return 0;

    }

    if(x==a-1)continue;

    return 0;

  }

  return 1;

}

LL PollardRho(LL n,LL a)

{

  srand((unsigned int)time(NULL));

  LL x=rand()%n,y=x,gcd=1,k=0,i=1;

  while(gcd==1)

  {

    k++;

    x=Mult(x,x,n)+a;if(x>=n)x-=n;

    gcd=GCD(x>y?x-y:y-x,n);

    if(k==i){y=x;i<<=1;}

  }

  if(gcd==n)return PollardRho(n,a+1);

  return gcd;

}

int main(void)

{

  LL a=0,p=1,q=-1,N=IN();

  if(N<=1)return puts("0"),0;

  Exp(N,2);a=e[count[1]];N=count[0];

  Exp(N,3);a+=e[count[1]];N=count[0];

  while(q*q<=UnUseMethod)

  {

    p+=6,q+=6;

    Exp(N,p);a+=e[count[1]];N=count[0];

    Exp(N,q);a+=e[count[1]];N=count[0];

  }

  if(N<=UnUseMethod){if(N>1){a++;}return printf("%lld\n",a),0;}

  if(MillerRabin(N)){a++;return printf("%lld\n",a),0;}

  while(N>=UnUseMethod)

  {

    p=PollardRho(N,0);

    while(!MillerRabin(p))p=PollardRho(p,p);

    Exp(N,p);a+=e[count[1]];N=count[0];

  }

  if(MillerRabin(N)){a++;}return printf("%lld\n",a),0;

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

const int e[40]={0,1,1,2,2,2,3,3,3,3,4,4,4,4,4,5,5,5,5,5,

                 5,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,8,8,8,8};

int main(void)

{

  int i,x;

  long long a=0,N;

  x=scanf("%lld",&N)-1;

  while(N%2==0){x++;N/=2;}

  a+=e[x];

  for(i=3;i<=1e6;i+=2)

  {

    x=0;while(!(N%i))x++,N/=i;

    a+=e[x];

  }

  if(N>1)a++;

  return printf("%lld\n",a),0;

}

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

#include<stdlib.h>

#include<time.h>

typedef long long LL;

const int e[40]={0,1,1,2,2,2,3,3,3,3,4,4,4,4,4,5,5,5,5,5,

               5,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,8,8,8,8};

const LL UnUseMethod=11e11;

LL count[2]={0};

LL IN(void)

{

  LL x=0;short f=0,c=getchar();while(c<48||c>57){f^=c==45,c=getchar();}

  while(c>47&&c<58){x=x*10+c-48,c=getchar();}return f?-x:x;

}

LL GCD(LL a,LL b){return !b?a:GCD(b,a%b);}

LL Mult(LL x,LL y,LL mod)

{LL temp=x*y-(LL)((long double)x/mod*y+1e-8)*mod;return temp<0?temp+mod:temp;}

LL BinaryModularPower(LL base,LL pow,LL mod)

{

  LL x=1;

  while(pow){if(pow&1){x=Mult(x,base,mod);}base=Mult(base,base,mod);pow>>=1;}

  return x;

}

LL f(LL x,LL mod,LL c){return (Mult(x,x,mod)+c)%x+1;}

void Exp(LL x,LL y){count[1]=0;while(!(x%y)){count[1]++;x/=y;}count[0]=x;return;}

int MillerRabin(const LL a)

{

  if(a==2)return 1;

  if(a%2==0||a==1)return 0;

  static int pr[7]={2,325,9375,28178,450775,9780504,1795265022};

  LL u=a-1,t=0,p=1;

  while(!(u&1)){u>>=1;t++;}

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

  {

    p=pr[i]%a;

    if(!p)return 1;

    LL x=BinaryModularPower(p,u,a);

    if(x==1)continue;

    for(int j=0;x!=a-1&&j<t;++j)

    {

      x=Mult(x,x,a);

      if(x==1)return 0;

    }

    if(x==a-1)continue;

    return 0;

  }

  return 1;

}

LL PollardRho(LL n,LL a)

{

  srand((unsigned int)time(NULL));

  LL x=rand()%n,y=x,gcd=1,k=0,i=1;

  while(gcd==1)

  {

    k++;

    x=Mult(x,x,n)+a;if(x>=n)x-=n;

    gcd=GCD(x>y?x-y:y-x,n);

    if(k==i){y=x;i<<=1;}

  }

  if(gcd==n)return PollardRho(n,a+1);

  return gcd;

}

int main(void)

{

  LL a=0,p=1,q=-1,N=IN();

  if(N<=1)return puts("0"),0;

  Exp(N,2);a=e[count[1]];N=count[0];

  Exp(N,3);a+=e[count[1]];N=count[0];

  while(q*q<=UnUseMethod)

  {

    p+=6,q+=6;

    Exp(N,p);a+=e[count[1]];N=count[0];

    Exp(N,q);a+=e[count[1]];N=count[0];

  }

  if(N<=UnUseMethod){if(N>1){a++;}return printf("%lld\n",a),0;}

  if(MillerRabin(N)){a++;return printf("%lld\n",a),0;}

  while(N>=UnUseMethod)

  {

    p=PollardRho(N,0);

    while(!MillerRabin(p))p=PollardRho(p,p);

    Exp(N,p);a+=e[count[1]];N=count[0];

  }

  if(MillerRabin(N)){a++;}return printf("%lld\n",a),0;

}
// Slower C++ solution:
#include <iostream>

#include <utility>

#include <vector>

using ll=long long;

#define rep(i,a,b) for(ll i=a;i<ll(b);i++)

#define repr(i,a,b) for(ll i=a;i>=ll(b);i--)

#define endl "\n"

#define ALL(x) x.begin(),x.end()

#define ALLR(x) x.rbegin(),x.rend()

using namespace std;



using P=pair<ll, ll>;

vector<P> prime_factorize(ll N) {

    vector<P> res;

    for (ll a = 2; a*a <= N; a++) {

        if (N % a != 0) continue;

        ll ex = 0; // 指数



        // 割れる限り割り続ける

        while (N % a == 0) {

            ex++;

            N /= a;

        }



        // その結果を push

        res.push_back(P(a, ex));

    }



    // 最後に残った数について

    if (N != 1) res.push_back(P(N, 1));

    return res;

}



const int MAX = 1e6;



ll N, ans;

vector<ll> pCount(MAX);

int main() {

	cin >> N;



	// 素因分解

	const auto &res = prime_factorize(N);

    rep(i, 0, res.size()) {

		int a = res[i].second;



		int b = 1;

		while(1){

			a -= b;

			if(a < 0) break;

			ans++;

			b++;

		}

    }

	cout << ans << endl;



    return 0;

}


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

#include <utility>

#include <vector>

#include <string>

#include <algorithm>

#include <cmath>

using namespace std;

using ll=long long;

#define rep(i,a,b) for(ll i=a;i<ll(b);i++)

#define repr(i,a,b) for(ll i=a;i>=ll(b);i--)

#define endl "\n"

#define ALL(x) x.begin(),x.end()

#define ALLR(x) x.rbegin(),x.rend()

#define INF 1e9

#define DEBUG(x) cout<<"debug: "<<x<<endl



vector<pair<ll, ll>> GetPrimes(ll parm){

    // first: prime, second: ex

    vector<pair<ll, ll>> res;



    ll ex = 0;

    while (parm % 2 == 0) {

        ex++;

        parm /= 2;

    }

    if(ex != 0) res.push_back({2, ex});



    for(ll i = 3; i*i <= parm; i += 2 ){

        ex = 0;

        while(parm % i == 0){

            ex++;

            parm /= i;

        }

        if(ex != 0) res.push_back({i, ex});

    }



    if(parm != 1) res.push_back({parm, 1});

    return res;

}



ll n, ans;

int main() {

    cin >> n;

    const auto &res = GetPrimes(n);



    for(auto p : res){

        ll ex = p.second;

        int i = 1;

        while(ex > 0){

            ex -= i; i++;

            if(ex >= 0) ans++;

        }

    }



    cout << ans << endl;



    return 0;

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

using namespace std;

#define ll long long

const int N=2005;

int n,sz[N];ll ans=1e18,f[N],g[N];

char s[N];vector<int>G[N];

void dfs(int x,int p)

{

	sz[x]=s[x]=='1';g[x]=0;ll mx=0,sum=0;

	for(int i=0;i<G[x].size();i++)if(G[x][i]!=p)

	{

		int y=G[x][i];dfs(y,x);sz[x]+=sz[y];

		g[y]+=sz[y];g[x]+=g[y];f[y]+=sz[y];

		if(f[y]>=f[mx])sum+=g[mx],mx=y;else sum+=g[y];

	}

	if(sum>=f[mx])f[x]=(sum-f[mx])&1;else f[x]=f[mx]-sum;

}

int main()

{

	scanf("%d%s",&n,s+1);

	for(int i=1,u,v;i<n;i++)scanf("%d%d",&u,&v),G[u].push_back(v),G[v].push_back(u);

	for(int i=1;i<=n;i++){dfs(i,0);if(!f[i])ans=min(ans,g[i]);}

	printf("%d\n",ans==1e18?-1:ans/2);return 0;

}

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

#include<algorithm>

using namespace std;

#define N 2050

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

int head[N],cnt,n,mn[N],mx[N],sz[N],a,b,as=1e9;

char is[N];

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)

{

	sz[u]=(is[u]=='1');mn[u]=mx[u]=0;

	for(int i=head[u];i;i=ed[i].next)if(ed[i].t!=fa)dfs(ed[i].t,u),mx[u]+=mx[ed[i].t]+sz[ed[i].t],sz[u]+=sz[ed[i].t];

	for(int i=head[u];i;i=ed[i].next)if(ed[i].t!=fa)mn[u]=max(mn[u],mn[ed[i].t]+mx[ed[i].t]-mx[u]+sz[ed[i].t]*2);

}

int main()

{

	scanf("%d%s",&n,is+1);

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

	for(int i=1;i<=n;i++)dfs(i,0),as=min(as,(mn[i]||(mx[i]&1))?1000000000:mx[i]/2);

	printf("%d\n",as>1e8?-1:as);

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

using namespace std;

#define ll long long

const int N=2005;

int n,sz[N];ll ans=1e18,f[N],g[N];

char s[N];vector<int>G[N];

void dfs(int x,int p)

{

	sz[x]=s[x]=='1';g[x]=0;ll mx=0,sum=0;

	for(int i=0;i<G[x].size();i++)if(G[x][i]!=p)

	{

		int y=G[x][i];dfs(y,x);sz[x]+=sz[y];

		g[y]+=sz[y];g[x]+=g[y];f[y]+=sz[y];

		if(f[y]>=f[mx])sum+=g[mx],mx=y;else sum+=g[y];

	}

	if(sum>=f[mx])f[x]=(sum-f[mx])&1;else f[x]=f[mx]-sum;

}

int main()

{

	scanf("%d%s",&n,s+1);

	for(int i=1,u,v;i<n;i++)scanf("%d%d",&u,&v),G[u].push_back(v),G[v].push_back(u);

	for(int i=1;i<=n;i++){dfs(i,0);if(!f[i])ans=min(ans,g[i]);}

	printf("%d\n",ans==1e18?-1:ans/2);return 0;

}

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

#include<algorithm>

using namespace std;

const int MAXN = 2000;

const int INF = (1<<30);

struct edge{

	int to; edge *nxt;

}edges[2*MAXN + 5], *adj[MAXN + 5], *ecnt=&edges[0];

void addedge(int u, int v) {

	edge *p = (++ecnt);

	p->to = v, p->nxt = adj[u], adj[u] = p;

	p = (++ecnt);

	p->to = u, p->nxt = adj[v], adj[v] = p;

}

int a[MAXN + 5], N;

int f[MAXN + 5], s[MAXN + 5];

void dfs(int x, int fa) {

	s[x] = a[x], f[x] = 0;

	for(edge *p=adj[x];p;p=p->nxt) {

		if( p->to == fa ) continue;

		dfs(p->to, x), s[x] += s[p->to];

		f[x] += f[p->to] + s[p->to];

	}

}

int get(int x, int fa) {

	int mx = 0;

	for(edge *p=adj[x];p;p=p->nxt) {

		if( p->to == fa ) continue;

		if( mx == 0 || f[p->to] > f[mx] ) mx = p->to;

	}

	if( mx == 0 ) return 0;

	int k = get(mx, x) + s[mx];

	if( f[x] - f[mx] - s[mx] >= k ) return f[x] & 1;

	else return k - (f[x] - f[mx] - s[mx]);

}

char S[MAXN + 5];

int main() {

	scanf("%d%s", &N, S + 1);

	for(int i=1;i<=N;i++) a[i] = S[i] - '0';

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

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

		addedge(u, v);

	}

	int ans = INF;

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

		dfs(j, 0);

		if( get(j, 0) == 0 )

			ans = min(ans, f[j]/2);

	}

	if( ans == INF ) printf("-1\n");

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

}

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

using namespace std;



const int N = 2010;



struct edge {

    int to, next;

} e[N * 2];



int head[N], ecnt;



inline void adde(int from, int to) {

    e[++ecnt] = (edge){to, head[from]}, head[from] = ecnt;

    e[++ecnt] = (edge){from, head[to]}, head[to] = ecnt;

}



// sum: 子树内棋子个数 dp: 子树内最少操作步数

int sum[N], dp[N];



int val[N];



void dfs(int u, int f) {

    sum[u] = val[u], dp[u] = 0;

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

        if (e[i].to != f) {

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

            sum[u] += sum[e[i].to], dp[u] += dp[e[i].to] + sum[e[i].to];

        }

}



// 子树的最小剩余深度

int dfs2(int u, int f) {

    int mx = 0;

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

        if (e[i].to != f) 

            if (dp[e[i].to] >= dp[mx]) 

                mx = e[i].to;

    if (!mx) return 0;

    int tmp = dfs2(mx, u) + sum[mx];

    if (dp[u] - dp[mx] - sum[mx] >= tmp) return dp[u] & 1;

    return tmp - (dp[u] - dp[mx] - sum[mx]);

}



char s[N];



int main() {

    int n; scanf("%d%s", &n, s + 1);

    for (int i = 1; i <= n; i++) val[i] = s[i] == '1';

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

    int res = 1e9;

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

        dfs(i, 0);

        if (!dfs2(i, 0)) res = min(res, dp[i] / 2);

    }

    if (res < 1e8) printf("%d\n", res);

    else puts("-1");

    return 0;

}//

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

#include<algorithm>

using namespace std;

const int MAXN = 2000;

const int INF = (1<<30);

struct edge{

	int to; edge *nxt;

}edges[2*MAXN + 5], *adj[MAXN + 5], *ecnt=&edges[0];

void addedge(int u, int v) {

	edge *p = (++ecnt);

	p->to = v, p->nxt = adj[u], adj[u] = p;

	p = (++ecnt);

	p->to = u, p->nxt = adj[v], adj[v] = p;

}

int a[MAXN + 5], N;

int f[MAXN + 5], s[MAXN + 5];

void dfs(int x, int fa) {

	s[x] = a[x], f[x] = 0;

	for(edge *p=adj[x];p;p=p->nxt) {

		if( p->to == fa ) continue;

		dfs(p->to, x), s[x] += s[p->to];

		f[x] += f[p->to] + s[p->to];

	}

}

int get(int x, int fa) {

	int mx = 0;

	for(edge *p=adj[x];p;p=p->nxt) {

		if( p->to == fa ) continue;

		if( mx == 0 || f[p->to] > f[mx] ) mx = p->to;

	}

	if( mx == 0 ) return 0;

	int k = get(mx, x) + s[mx];

	if( f[x] - f[mx] - s[mx] >= k ) return f[x] & 1;

	else return k - (f[x] - f[mx] - s[mx]);

}

char S[MAXN + 5];

int main() {

	scanf("%d%s", &N, S + 1);

	for(int i=1;i<=N;i++) a[i] = S[i] - '0';

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

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

		addedge(u, v);

	}

	int ans = INF;

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

		dfs(j, 0);

		if( get(j, 0) == 0 )

			ans = min(ans, f[j]/2);

	}

	if( ans == INF ) printf("-1\n");

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

}

//
// Slower C++ solution:
#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define N 2005

#define inf 0x3f3f3f3f

int n;

int fir[N], tar[N << 1], nex[N << 1], cnt;

int mn[N], mx[N], siz[N];

int now, tot, ans = inf;

char S[N];

void Add(int a, int b)

{

	++cnt;

	tar[cnt] = b;

	nex[cnt] = fir[a];

	fir[a] = cnt;

}

void Dfs(int r, int fa, int d)

{

	if (S[r] == '1')

		now += d;

	for (int i = fir[r]; i; i = nex[i])

	{

		int v = tar[i];

		if (v == fa)

			continue;

		Dfs(v, r, d + 1);

	}

}

void Dfs1(int r, int fa, int d)

{

	if (S[r] == '1')

		tot += d;

	for (int i = fir[r]; i; i = nex[i])

	{

		int v = tar[i];

		if (v == fa)

			continue;

		Dfs1(v, r, d + 1);

	}

}

void Dfs2(int r, int fa)

{

	int tot = 0, p = 0;

	siz[r] = S[r] - '0';

	for (int i = fir[r]; i; i = nex[i])

	{

		int v = tar[i];

		if (v == fa)

			continue;

		Dfs2(v, r);

		if (mn[v] > mn[p])

			p = v;

		tot += mx[v];

		siz[r] += siz[v];

	}

	mx[r] = tot;

	tot -= mx[p];

	mn[r] = max(0, mn[p] - tot);

	if (fa)

	{

		mn[r] += siz[r];

		mx[r] += siz[r];

	}

}

void Solve(int r)

{

	tot = 0;

	Dfs1(r, 0, 0);

	if (tot & 1)

		return;

	Dfs2(r, 0);

	if (mn[r] > 0)

		return;

	ans = min(ans, tot / 2);

}

int main()

{

	scanf("%d%s", &n, S + 1);

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

	{

		int a, b;

		scanf("%d%d", &a, &b);

		Add(a, b), Add(b, a);

	}

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

		Solve(i);

	if (ans == inf)

		puts("-1");

	else

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

}


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

#include<algorithm>

using namespace std;

const int MAXN = 2000;

const int INF = (1<<30);

struct edge{

	int to; edge *nxt;

}edges[2*MAXN + 5], *adj[MAXN + 5], *ecnt=&edges[0];

void addedge(int u, int v) {

	edge *p = (++ecnt);

	p->to = v, p->nxt = adj[u], adj[u] = p;

	p = (++ecnt);

	p->to = u, p->nxt = adj[v], adj[v] = p;

}

int a[MAXN + 5], N;

int f[MAXN + 5], s[MAXN + 5];

void dfs(int x, int fa) {

	s[x] = a[x], f[x] = 0;

	for(edge *p=adj[x];p;p=p->nxt) {

		if( p->to == fa ) continue;

		dfs(p->to, x), s[x] += s[p->to];

		f[x] += f[p->to] + s[p->to];

	}

}

int get(int x, int fa) {

	int mx = 0;

	for(edge *p=adj[x];p;p=p->nxt) {

		if( p->to == fa ) continue;

		if( mx == 0 || f[p->to] > f[mx] ) mx = p->to;

	}

	if( mx == 0 ) return 0;

	int k = get(mx, x) + s[mx];

	if( f[x] - f[mx] - s[mx] >= k ) return f[x] & 1;

	else return k - (f[x] - f[mx] - s[mx]);

}

char S[MAXN + 5];

int main() {

	scanf("%d%s", &N, S + 1);

	for(int i=1;i<=N;i++) a[i] = S[i] - '0';

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

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

		addedge(u, v);

	}

	int ans = INF;

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

		dfs(j, 0);

		if( get(j, 0) == 0 )

			ans = min(ans, f[j]/2);

	}

	if( ans == INF ) printf("-1\n");

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

}

//