思路：树形DFS

本题其实就是统计子树中有多少个节点既有红色节点，又有黑色节点。我们可以自顶向下来进行DFS

遍历到$u$节点时，首先根据$u$节点是红/黑，来对变量进行初始化

然后我们可以遍历$u$的所有子节点，去将以$u$为根节点的红/黑节点数量进行累加计算。

最后判断以$u$为子树的根节点的红色和黑色节点数量是否都大于0，若大于0，则答案+1

C++

#include<bits/stdc++.h>
using namespace std;
const int N=1E5+10;
typedef long long ll;
int n,res;
string s;
vector<int>g[N];
vector<int> dfs(int u,int fa){
    vector<int>color(2,0);
    if(s[u]=='B')color[0]++;
    else color[1]++;
    for(int &x:g[u]){  //遍历子树
        if(x==fa)continue;
        auto v=dfs(x,u);
        color[0]+=v[0];
        color[1]+=v[1];
    }
    if(color[0]>0&&color[1]>0)res++;
    return color;
}
int main(){
    cin>>n;
    cin>>s;
    s=" "+s;
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1,0);
    cout<<res<<endl;
    return 0;
}

java

import java.util.*;
import java.io.*;
// 注意类名必须为Main
class Main {
    static int n;
    static Node[] nodes;
    static int res = 0;
    public static int aaa(){
        dfs(1,new HashMap<>());
        return res;
    }
    public static int dfs(int nodeIndex,HashMap<Integer,Integer> visited){
        visited.put(nodeIndex,0);
        Node node = nodes[nodeIndex];
        boolean red = node.color=='R'?true:false;
        boolean black = node.color=='B'?true:false;
        for(int i:node.children.keySet()){
            if(visited.get(i) != null){
                continue;
            }
            int num = dfs(i,visited);
            if(num == 0){
                black = true;
            }else if(num == 1){
                red = true;
            }else{
                black = true;
                red = true;
            }
        }
        if(red && black){
            res++;
            return 2;
        }
        return red?1:0;
    }
    public static void main(String[] args) throws Exception {
        // Scanner sc = new Scanner(System.in);
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(reader.readLine());
        // int b = sc.nextInt();
        nodes = new Node[n+1];
        String s = reader.readLine();
        for(int i=1;i<=n;i++){
            nodes[i] = new Node();
            nodes[i].color = s.charAt(i-1);
        }
        for(int i=1;i<n;i++){
            String[] ss = reader.readLine().split(" ");
            int u = Integer.parseInt(ss[0]);
            int v = Integer.parseInt(ss[1]);
            nodes[u].children.put(v,0);
            nodes[v].children.put(u,0);
        }
        System.out.println(aaa());
    }
}
class Node{
    // int father;
    HashMap<Integer,Integer> children = new HashMap<>();
    char color;
}

python

import sys
sys.setrecursionlimit(200000)
n=int(input())
color = input()
adj=[[] for _ in range(n)]
for _ in range(n-1):
    u,v = map(int,input().split())
    adj[u-1].append(v-1)
# print(adj)
count = 0

def dfs(i):
    global count
    if len(adj[i])==0:
        return False
    flag = False
    for j in adj[i]:
        if dfs(j):
            flag = True
        else:
            if color[i] != color[j]:
                flag = True
    if flag == True:
        count +=1
    return flag
dfs(0)
print(count)

题目描述

小美有一棵有$n$个节点的树，根节点为1号节点，树的每个节点是红色或者黑色，她想知道有多少节点的子树中同时包含红点和黑点。

输入描述

第一行输入一个整数$n(1\le n\le 10^5)$表示节点数量 第二行输入一个长度为$n$的字符串$s$表示节点的颜色，第$i$个节点的颜色为$s_i$，若$s_i$为'B'表示节点的颜色为黑色，若$s_i$为'R' 则表示节点的颜色为红色。 接下来$n -1$行，每行输入两个整数 $u,v(1\le u,\le n)$表示树上的边.

输出描述

输出一个整数表示答案。

样例

输入

3
BRB
1 2
2 3

输出

2