Submission #2503794

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
using Int = long long;

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}

template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
  for(auto &e:t) fill_v(e,v);
}


template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
signed main(){
  Int n;
  cin>>n;
  vector<vector<Int> > G(n);
  for(Int i=1;i<n;i++){
    Int x,y;
    cin>>x>>y;
    x--;y--;
    G[x].emplace_back(y);
    G[y].emplace_back(x);
  }
  string s;
  cin>>s;

  if(n==1){
    cout<<(s[0]=='W')<<endl;
    return 0;
  }

  Int ans=0,dec=0;
  auto dp=make_v<Int>(2,n);
  fill_v(dp,0);
  vector<Int> ok(n,0);
  vector<Int> cnt(n,0);
  
  function<void(Int, Int)> dfs=[&](Int v,Int p)->void{
    cnt[v]=(p!=-1);
    ok[v]=s[v]=='W';

    using P = pair<Int, Int>;
    vector<P> vp1,vp2;
    vp1.emplace_back(0,-1);
    vp2.emplace_back(0,-1);
    vp1.emplace_back(0,-1);
    vp2.emplace_back(0,-1);
    
    for(Int u:G[v]){
      if(u==p) continue;
      dfs(u,v);
      if(!ok[u]) continue;
      ok[v]=1;
      chmax(dp[0][v],dp[0][u]+(cnt[u]%2 != (s[u]=='W')));
      chmax(dp[1][v],dp[1][u]);
      vp1.emplace_back(dp[0][u]+(cnt[u]%2 != (s[u]=='W')),u);      
      vp2.emplace_back(dp[1][u],u);
      ans+=2;      
      cnt[v]++;      
    }    
    if(!ok[v]) return;
    //cout<<v<<":"<<dp[0][v]<<" "<<dp[1][v]<<endl;
    
    for(Int i=0;i<(Int)vp2.size();i++){
      if(vp2[i].second<0) continue;
      vp2[i].first+=(cnt[v]%2 != (s[v]=='W'));
    }
    
    dp[1][v]+=(cnt[v]%2 != (s[v]=='W'));
    if(cnt[v]%2 != (s[v]=='W')) ans++;
    //cout<<v<<":"<<cnt[v]<<" "<<s[v]<<":"<<(cnt[v]%2 != (s[v]=='W'))<<endl;
    
    sort(vp1.rbegin(),vp1.rend());
    sort(vp2.rbegin(),vp2.rend());

    //cout<<v<<":"<<vp1[0].first<<" "<<vp2[0].first<<endl;
    //cout<<v<<":"<<vp1[0].first+vp2[vp1[0].second==vp2[0].second].first<<endl;
    //cout<<v<<":"<<vp2[0].first+vp1[vp1[0].second==vp2[0].second].first<<endl;
    
    chmax(dec,vp1[0].first+vp2[vp1[0].second==vp2[0].second].first);
    chmax(dec,vp2[0].first+vp1[vp1[0].second==vp2[0].second].first);
  };

  Int r=-1;
  for(Int i=0;i<n;i++){
    if(s[i]=='B') continue;
    dfs(r=i,-1);
    break;
  }

  //cout<<ans<<endl;
  cout<<ans-dec*2<<endl;
  return 0;
}

Submission Info

Judge Result