题目思路

第一遍dfs求解这棵树上每个子树的大小$sz[i]$以及每个子树中红色结点的个数$r[i]$ . 我们假设1为根节点

第二遍dfs，枚举每条边$(u,v)$，考虑将这条边删掉之后，子树的红色结点个数为$r[v]$ , 蓝色结点个数就是$sz[v] - r[v]$. 另一个颗树的红色结点个数就是$r[1] - r[v]$ . 蓝色结点个数就是$sz[1] - r[1] - (sz[v] - r[v])$

判断一下是不是都 红色 > 蓝色即可

类似题目:

P1170 2023.04.08-美团春招-第五题-RGB树

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn =1e5 + 5;
string a;
// 矢量版邻接矩阵 , 存每个点的邻接点
vector<int> e[maxn];
// sz , r 含义如上
int sz[maxn] , r[maxn];
// 第一遍 dfs 求出每个点的 sz 和 r 
void dfs1 (int u , int fa){
    sz[u] = 1;
    r[u] = a[u] == 'R';
    for (auto v : e[u]){
        if (v == fa) continue;
        dfs1(v , u);
        sz[u] += sz[v];
        r[u] += r[v];
    }
    return ;
}
// 第二遍 枚举每条边(u,v)
int ans = 0;
void dfs2 (int u , int fa){
    for (auto v : e[u]){
        if (v == fa) continue;
        dfs2(v , u);
        // 判断子树是否合法
        if (r[v] <= sz[v] - r[v]) continue;
        // 判断主树是否合法
        int rest_sz = sz[1] - sz[v];
        int rest_r = r[1] - r[v];
        if (rest_r <= rest_sz - rest_r) continue;
        // 都合法，则这条边可以，答案 + 1
        ans++;
    }
    return ;
}
int main (){
    int n;
    cin >> n;
    cin >> a;
    // 读入
    a = '#' + a;
    for (int i = 1 ; i < n ; i++){
        int x , y;
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs1(1 , -1);
    dfs2(1 , -1);
    cout << ans << endl;
    return 0;
}

题目内容

曾经有一个叫做小红的年轻人，他是一个热衷于研究二叉树的数学家。他认为，一棵树只有当它的红色节点数量大于蓝色节点数量时才是好树。他的定义引起了人们的热议，有些人同意他的定义，有些人则持不同意见。但无论怎样，这个定义还是被广泛地接受了。

有一天，小红发现了一棵好树，但他觉得它不够完美。于是他开始思考，如果能够将这棵好树分成两个好树，那它就更加完美了。

经过一番研究，他发现只需要删除一条边，就可以将这棵树分成两个好树。他想知道有多少种删除边的方案，于是他向你求助。

输入描述

第一行输入一个正整数 $n$ ，代表节点的数量。

第二行输入一个长度为 $n$ 的，仅包含 'R' 和 'B' 两种字符的字符串，第 $i$ 个字符为 'R' 代表第 $i$ 个节点被染成红色，'B'代表被染成蓝色。

接下来的 $n -1$ 行，每行输入两个正整数 $u$ 和 $v$ ，代表节点 $u$ 和节点 $v$ 有一条边连接。

$1\le n\le 10^5$

输出描述

一个整数，代表删边的方案数。

样例

输入

5
RRBRB
1 2
2 3
1 4
4 5

输出

0

样例解释

无论删除哪条边，都会导致有一个子树不是好树。