题解 | 颜色交错路径计数

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

int main() {
    int n;
    cin >> n;
    vector<vector<int>> g(n + 1);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    string s;             // s[i-1] 为第 i 个节点颜色：'B' 或 'R'
    cin >> s;
    vector<char> vis(n + 1, 0);
    long long ans = 0;
    for (int i = 1; i <= n; ++i) if (!vis[i]) {
            // 只沿“颜色不同”的边跑一遍连通分量
            long long sz = 0;
            stack<int> st;
            st.push(i);
            vis[i] = 1;
            while (!st.empty()) {
                int u = st.top();
                st.pop();
                ++sz;
                for (int v : g[u]) {
                    if (!vis[v] && s[u - 1] != s[v - 1]) {
                        vis[v] = 1;
                        st.push(v);
                    }
                }
            }
            ans += sz * (sz + 1) / 2;  // 该分量贡献
        }

    cout << ans << '\n';
    return 0;
}