Submission #2501455

---

Source Code Expand

// eddy1021
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod7=1000000007LL;
inline LL getint(){
  LL _x=0,_tmp=1; char _tc=getchar();    
  while( (_tc<'0'||_tc>'9')&&_tc!='-' ) _tc=getchar();
  if( _tc == '-' ) _tc=getchar() , _tmp = -1;
  while(_tc>='0'&&_tc<='9') _x*=10,_x+=(_tc-'0'),_tc=getchar();
  return _x*_tmp;
}
inline LL add(LL _x, LL _y, LL _mod=mod7){
  _x+=_y;
  return _x>=_mod ? _x-_mod : _x;
}
inline LL sub(LL _x, LL _y, LL _mod=mod7){
  _x-=_y;
  return _x<0 ? _x+_mod : _x;
}
inline LL mul(LL _x, LL _y ,LL _mod=mod7){
  _x*=_y;
  return _x>=_mod ? _x%_mod : _x;
}
LL mypow(LL _a, LL _x, LL _mod){
  if(_x == 0) return 1LL;
  LL _ret = mypow(mul(_a, _a, _mod), _x>>1, _mod);
  if(_x & 1) _ret=mul(_ret, _a, _mod);
  return _ret;
}
LL mymul(LL _a, LL _x, LL _mod){
  if(_x == 0) return 0LL;
  LL _ret = mymul(add(_a, _a, _mod), _x>>1, _mod);
  if(_x & 1) _ret=add(_ret, _a, _mod);
  return _ret;
}
void sleep(double sec = 1021){
  clock_t s = clock();
  while(clock() - s < CLOCKS_PER_SEC * sec);
}
#define Bye exit(0)
int __ = 1 , _cs;
/*********default*********/
const int N=101010;
void build(){

}
int n, vl[N];
vector<int> v[N];
char c[N];
void init(){
  n=getint();
  for(int i=1; i<n; i++){
    int ui=getint();
    int vi=getint();
    v[ui].push_back(vi);
    v[vi].push_back(ui);
  }
  scanf("%s", c+1);
  for(int i=1; i<=n; i++)
    vl[i]=(c[i] == 'W');
}
int root, sz[N];
void go(int now, int prt){
  sz[now]=(c[now] == 'W');
  for(int son: v[now]){
    if(son == prt) continue;
    go(son, now);
    sz[now]+=sz[son];
  }
}
int cnt[N], ans, bst, dp[N][2];
void DP(int now, int prt){
  for(int son: v[now]){
    if(son == prt or sz[son] == 0)
      continue;
    cnt[now] ++;
    DP(son, now);
    ans+=2;
  }
  for(int son: v[now]){
    if(son == prt or sz[son] == 0)
      continue;
    int tdp[2];
    tdp[0]=(1+(((vl[son]+cnt[son]+1)&1)?1:-1))+dp[son][0];
    tdp[1]=(1+(((vl[now]+cnt[now]+(now != prt))&1)?1:-1))+dp[son][1];
    bst=max(bst, tdp[0]+dp[now][1]);
    bst=max(bst, tdp[1]+dp[now][0]);
    dp[now][0]=max(dp[now][0], tdp[0]);
    dp[now][1]=max(dp[now][1], tdp[1]);
  }
  //printf("%d: %d %d\n", now, dp[now][0], dp[now][1]);
  ans+=(vl[now]+cnt[now]+(now!=prt))&1;
}
void solve(){
  for(int i=1; i<=n; i++)
    if(c[i] == 'W'){
      root=i;
      break;
    }
  if(!root){
    cout<<0<<endl;
    exit(0);
  }
  go(root, root);
  DP(root, root);
  cout<<ans-bst<<endl;
}
int main(){
  build();
  //__ = getint();
  while(__ --){
    init();
    solve();
  }
}

Submission Info

Compile Error

./Main.cpp: In function ‘void init()’:
./Main.cpp:60:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", c+1);
                   ^

Judge Result