F - Monochrome Cat | AtCoder Regular Contest 097

公式解説みて書いた

void dfs(int u, int p, int d, vector<vi> &H, vi &dist, vi &score) {
    dist[u] = d + score[u];
    each(v, H[u])if (v != p) {
        dfs(v, u, dist[u], H, dist, score);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);

    int N;
    cin >> N;
    vector<vi> G(N);
    rep(a, N - 1) {
        int x, y;
        cin >> x >> y;
        --x; --y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    string A;
    cin >> A;
    vi C(N);
    int nw = 0;
    rep(a, N) {
        char c = A[a];
        C[a] = c == 'W' ? 1 : 0;
        nw += C[a];
    }

    if (nw <= 1) {
        cout << nw << endl;
        return 0;
    }

    vi deg(N);
    queue<int> Q;
    rep(a, N) {
        deg[a] = sz(G[a]);
        if (deg[a]==1 && !C[a]) {
            Q.push(a);
        }
    }
    vector<bool> removed(N);
    while (sz(Q)) {
        int u = Q.front();
        removed[u] = true;
        Q.pop();
        each(v, G[u]) {
            if (--deg[v] == 1 && !C[v]) {
                Q.push(v);
            }
        }
    }

    fill(all(deg), 0);
    vector<vi> H(N);
    int V = 0;
    rep(u, N)if (!removed[u]) {
        V++;
        each(v, G[u])if (!removed[v]) {
            H[u].push_back(v);
            deg[u]++;
        }
    }

    // Euler Tourした場合のコスト
    // すべての頂点は(次数)回ずつ値変更
    int re = 2 * (V - 1), S = 0;
    vi score(N);
    rep(a, N) if(!removed[a]){
        int x = C[a] ^ (deg[a] & 1);
        re += x;
        score[a] = x;
        if(deg[a]==1)S = a;
    }

    // すべての頂点を訪れたらEuler Tourを打ち切る。
    // 残りのパス上の頂点は(次数-1)回ずつ値変更
    
    // 一番コストを減らせるパスを探す
    // 木の直径を求めるのと同じ
    vi dist(N);
    dfs(S, -1, 0, H, dist, score);
    rep(a, N)if (!removed[a]) {
        if (dist[S] < dist[a] && deg[a] == 1)S = a;
    }
    dfs(S, -1, 0, H, dist, score);
    int ma = 0;
    rep(a, N)if (!removed[a]) smax(ma, dist[a]);
    re -= 2*ma;
    cout << re << endl;
}