Language: C++

#include<bits/stdc++.h>

using namespace std;

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5 + 5;

int N;

vector<int> adj[MAXN];
int edges[MAXN];
char col[MAXN];
bool removed[MAXN];
int remain;

//if we travel each edge once in each direction, does this node need fixing?
int fixval(int x){
    return (edges[x] % 2 == 0 && col[x] == 'W') || (edges[x] % 2 == 1 && col[x] == 'B') ? 1 : -1;
}

int reduce = 0;

pii bestup[MAXN][3];
pii bestdown[MAXN][3];

void dfs(int pos, int par){
    bestup[pos][0] = pii(fixval(pos), pos);
    bestup[pos][1] = pii(-1e9, -1);
    bestup[pos][2] = pii(-1e9, -2);

    bestdown[pos][0] = pii(0, pos);
    bestdown[pos][1] = pii(-1e9, -1);
    bestdown[pos][2] = pii(-1e9, -2);

    for(int i : adj[pos]){
        if(i == par || removed[i]){
            continue;
        }
        dfs(i, pos);

        pii up = pii(bestup[i][0].first + 1 + fixval(pos), i);
        pii down = pii(bestdown[i][0].first + 1 + fixval(pos), i);

        //cout << pos << " from " << i << " get " << up.first << " and " << down.first << endl;

        if(up > bestup[pos][0]){
            bestup[pos][2] = bestup[pos][1];
            bestup[pos][1] = bestup[pos][0];
            bestup[pos][0] = up;
        } else if (up > bestup[pos][1]){
            bestup[pos][2] = bestup[pos][1];
            bestup[pos][1] = up;
        } else if (up > bestup[pos][2]){
            bestup[pos][2] = up;
        }

        if(down > bestdown[pos][0]){
            bestdown[pos][2] = bestdown[pos][1];
            bestdown[pos][1] = bestdown[pos][0];
            bestdown[pos][0] = down;
        } else if (down > bestdown[pos][1]){
            bestdown[pos][2] = bestdown[pos][1];
            bestdown[pos][1] = down;
        } else if (down > bestdown[pos][2]){
            bestdown[pos][2] = down;
        }
    }
    
    if(bestup[pos][0].second == pos){
        reduce = max(reduce, bestup[pos][1].first - fixval(pos));
    } else {
        reduce = max(reduce, bestup[pos][0].first - fixval(pos));
    }

    if(bestdown[pos][0].second == pos){
        reduce = max(reduce, bestdown[pos][1].first);
    } else {
        reduce = max(reduce, bestdown[pos][0].first);
    }

    for(int a = 0; a < 3; a++){
        for(int b = 0; b < 3; b++){
            if(bestup[pos][a].second == bestdown[pos][b].second){
                continue;
            }
            
            if(bestup[pos][a].second == pos){
                continue;
            }

            if(bestdown[pos][b].second == pos){
                continue;
            }

            reduce = max(reduce, bestup[pos][a].first + bestdown[pos][b].first - fixval(pos));
        }
    }

    cout << pos << " has\n";
    for(int a = 0; a < 3; a++){
        cout << "[" << bestup[a].first << ", " << bestup[a].second << "]";
        cout << "[" << bestdown[a].first << ", " << bestdown[a].second << "]";
        cout << endl;
    }
    cout << endl;
}

int main(){
    cin.tie(0);
    cin.sync_with_stdio(0);

    cin >> N;
    
    remain = N;
    for(int a = 1; a <= N - 1; a++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);

        edges[u]++;
        edges[v]++;
    }

    cin >> (col + 1);

    if(N == 1){
        cout << (col[1] == 'W');
        return 0;
    }

    queue<int> q;
    for(int a = 1; a <= N; a++){
        if(edges[a] == 1 && col[a] == 'B'){
            q.push(a);
        }
    }

    while(!q.empty()){
        int fr = q.front();
        q.pop();

        remain--;
        removed[fr] = true;

        for(int i : adj[fr]){
            edges[i]--;
            if(edges[i] == 1 && col[i] == 'B'){
                q.push(i);
            }
        }
    }

    if(remain == 0){
        cout << 0;
        return 0;
    }

    int start = -1;
    for(int a = 1; a <= N; a++){
        if(!removed[a]){
            start = a;
            break;
        }
    }

    if(start == -1){
        cout << 0;
    } else if (remain == 1){
        cout << (col[start] == 'W');
    } else if (remain == 2){
        cout << 2;
    } else {
        int ans = 2 * (remain - 1);
        for(int a = 1; a <= N; a++){
            if(!removed[a] && fixval(a) == +1){
                ans++;
            }
        }

        dfs(start, -1);

        cout << ans - reduce;
    }
}


Compiler output:
a.cc: In function 'void dfs(int, int)':
a.cc:75:9: error: reference to 'reduce' is ambiguous
   75 |         reduce = max(reduce, bestup[pos][1].first - fixval(pos));
      |         ^~~~~~
In file included from /usr/include/c++/14/numeric:739,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:58,
                 from a.cc:1:
/usr/include/c++/14/pstl/glue_numeric_defs.h:31:1: note: candidates are: 'template<class _ExecutionPolicy, class _ForwardIterator> __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, typename std::iterator_traits<_II>::value_type> std::reduce(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator)'
   31 | reduce(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last);
      | ^~~~~~
/usr/include/c++/14/pstl/glue_numeric_defs.h:26:1: note:                 'template<class _ExecutionPolicy, class _ForwardIterator, class _Tp> __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2> std::reduce(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _Tp)'
   26 | reduce(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Tp __init);
      | ^~~~~~
/usr/include/c++/14/pstl/glue_numeric_defs.h:21:1: note:                 'template<class _ExecutionPolicy, class _ForwardIterator, class _Tp, class _BinaryOperation> __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2> std::reduce(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _Tp, _BinaryOperation)'
   21 | reduce(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Tp __init,
      | ^~~~~~
/usr/include/c++/14/numeric:342:5: note:                 'template<class _InputIterator> typename std::iterator_traits< <template-parameter-1-1> >::value_type std::reduce(_InputIterator, _InputIterator)'
  342 |     reduce(_InputIterator __first, _InputIterator __last)
      |     ^~~~~~
/usr/include/c++/14/numeric:325:5: note:                 'template<class _InputIterator, class _Tp> _Tp std::reduce(_InputIterator, _InputIterator, _Tp)'
  325 |     reduce(_InputIterator __first, _InputIterator __last, _Tp __init)
      |     ^~~~~~
/usr/include/c++/14/numeric:287:5: note:                 'template<class _InputIterator, class _Tp, class _BinaryOperation> _Tp std::reduce(_InputIterator, _InputIterator, _Tp, _BinaryOperation)'
  287 |     reduce(_InputIterator __first, _InputIterator __last, _Tp __init,
      |     ^~~~~~
a.cc:26:5: note:                 'int reduce'
   26 | int reduce = 0;
      |     ^~~~~~
a.cc:75:22: error: reference to 'reduce' is ambiguous
   75 |         reduce = max(reduce, bestup[pos][1].first - fixval(pos));
      |                      ^~~~~~
/usr/include/c++/14/pstl/glue_numeric_defs.h:31:1: note: candidates are: 'template<class _ExecutionPolicy, class _ForwardIterator> __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, typename std::iterator_traits<_II>::value_type> std::reduce(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator)'
   31 | reduce(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last);
      | ^~~~~~
/usr/include/c++/14/pstl/glue_numeric_defs.h:26:1: note:                 'template<class _ExecutionPolicy, class _ForwardIterator, class _Tp> __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2> std::reduce(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _Tp)'
   26 | reduce(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Tp __init);
      | ^~~~~~
/usr/include/c++/14/pstl/glue_numeric_defs.h:21:1: note:                 'template<class _ExecutionPolicy, class _ForwardIterator, class _Tp, class _BinaryOperation> __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2> std::reduce(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _Tp, _BinaryOperation)'
   21 | reduce(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Tp __init,
      | ^~~~~~
/usr/include/c++/14/numeric:342:5: note:                 'template<class _InputIterator> typename std::iterator_traits< <template-parameter-1-1> >::value_type std::reduce(_InputIterator, _InputIterator)'
  342 |     reduce(_InputIterator __first, _InputIterator __last)
      |     ^~~~~~
/usr/include/c++/14/numeric:325:5: note:                 'template<class _InputIterator, class _Tp> _Tp std::reduce(_InputIterator, _InputIterator, _Tp)'
  325 |     reduce(_InputIterator __first, _InputIterator __last, _Tp __init)
      |     ^~~~~~
/usr/include/c++/14/numeric:287:5: note:                 'template<class _InputIterator, class _Tp, class _BinaryOperation> _Tp std::reduce(_InputIterator, _InputIterator, _Tp, _BinaryOperation)'
  287 |     reduce(_InputIterator __first, _InputIterator __last, _Tp __init,
      |     ^~~~~~
a.cc:26:5: note:                 'int reduce'
   26 | int reduce = 0;
      |     ^~~~~~
a.cc:77:9: error: reference to 'reduce' is ambiguous
   77 |         reduce = max(reduce, bestup[pos][0].first - fixval(pos));
      |         ^~~~~~
/usr/include/c++/14/pstl/glue_numeric_defs.h:31:1: note: candidates are: 'template<class _ExecutionPolicy, class _ForwardIterator> __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, typename std::iterator_traits<_II>::value_type> std::reduce(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator)'
   31 | reduce(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last);
      | ^~~~~~
/usr/include/c++/14/pstl/glue_numeric_defs.h:26:1: note:                 'template<class _ExecutionPolicy, class _ForwardIterator, class _Tp> __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2> std::reduce(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _Tp)'
   26 | reduce(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Tp __init);
      | ^~~~~~
/usr/include/c++/14/pstl/glue_numeric_defs.h:21:1: note:                 'template<class _ExecutionPolicy, class _ForwardIterator, class _Tp, class _BinaryOperation> __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2> std::reduce(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _Tp, _BinaryOperation)'
   21 | reduce(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Tp __init,
      | ^~~~~~
/usr/include/c++/14/numeric:342:5: note:                 'template<class _InputIterator> typename std::iterator_traits< <template-parameter-1-1> >::value_type std::reduce(_InputIterator, _InputIterator)'
  342 |     reduce(_InputIterator __first, _InputIterator __last)
      |     ^~~~~~
/usr/include/c++/14/numeric:325:5: note:                 'template<class _InputIterator, class _Tp> _Tp std::reduce(_InputIterator, _InputIterator, _Tp)'
  325 |     reduce(_InputIterator __first, _InputIterator __last, _Tp __init)
      |     ^~~~~~
/usr/include/c++/14/numeric:287:5: note:                 'template<class _InputIterator, class _Tp, class _BinaryOperation> _Tp std::reduce(_InputIterator, _InputIterator, _Tp, _BinaryOperation)'
  287 |     reduce(_InputIterator __first, _InputIterator __last, _Tp __init,
      |     ^~~~~~
a.cc:26:5: note:                 'int reduce'
   26 | int reduce = 0;
      |     ^~~~~~
a.cc:77:22: error: reference to 'reduce' is ambiguous
   77 |         reduce = max(reduce, bestup[pos][0].first - fixval(pos));
      |                      ^~~~~~
/usr/include/c++/14/pstl/glue_numeric_defs.h:31:1: note: candidates are: 'template<class _ExecutionPolicy, class _ForwardIterator> __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, typename std::iterator_traits<_II>::value_type> std::reduce(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator)'
   31 | reduce(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last);
      | ^~~~~~
/usr/include/c++/14/pstl/glue_numeric_defs.h:26:1: note:                 'template<class _ExecutionPolicy, class _ForwardIterator, class _Tp> __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2> std::reduce(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _Tp)'
   26 | reduce(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Tp __init);
      | ^~~~~~
/usr/include/c++/14/pstl/glue_numeric_defs.h:21:1: note:                 'template<class _ExecutionPolicy, class _ForwardIterator, class _Tp, class _BinaryOperation> __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2> std::reduce(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _Tp, _BinaryOperation)'
   21 | reduce(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Tp __init,
      | ^~~~~~
/usr/include/c++/14/numeric:342:5: note:                 'template<class _InputIterator> typename std::iterator_traits< <template-parameter-1-1> >::value_type std::reduce(_InputIterator, _InputIterator)'
  342 |     reduce(_InputIterator __first, _InputIterator __last)
      |     ^~~~~~
/usr/include/c++/14/numeric:325:5: note:                 'template<class _InputIterator, class _Tp> _Tp std::reduce(_InputIterator, _InputIterator, _Tp)'
  325 |     reduce(_InputIterator __first, _InputIterator __last, _Tp __init)
      |     ^~~~~~
/usr/include/c++/14/numeric:287:5: note:                 'template<class _InputIterator, class _Tp, class _BinaryOperation> _Tp std::reduce(_InputIterator, _InputIterator, _Tp, _BinaryOperation)'
  287 |     reduce(_InputIterator __first, _InputIterator __last, _Tp __init,
      |     ^~~~~~
a.cc:26:5: note:                 'int reduce'
   26 | int reduce = 0;
      |     ^~~~~~
a.cc:81:9: error: reference to 'reduce' is ambiguous
   81 |         reduce = max(reduce, bestdown[pos][1].first);
      |         ^~~~~~
/usr/include/c++/14/pstl/glue_numeric_defs.h:31:1: note: candidates are: 'template<class _ExecutionPolicy, class _ForwardIterator> __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, typename std::iterator_traits<_II>::value_type> std::reduce(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator)'
   31 | reduce(_ExecutionP