题解 | 小红的树切割

遍历树的每条边，检查端点颜色，如果相同就意味着这条边需要剪掉。

#include <iostream>
#include <map>
#include <vector>
using namespace std;

// int 是结点
// vector 是与该结点相连的所有结点
map<int, vector<int>> tree;
int ans = 0;
string s;

void dfs(int cur, int last) {
    for (auto next : tree[cur]) {
        // 不能往回走
        if (next == last) {
            continue;
        }
        // 颜色相同
        if (s[cur - 1] == s[next - 1]) {
            // 剪掉
            ans++;
        }
        // 继续检查下一条边
        dfs(next, cur);
    }
}

int main() {
    int n;
    cin >> n >> s;
    n--;
    while (n--) {
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    dfs(1, 0);
    cout << ans << endl;
}