首页 > 试题广场 >

游游的三色树

[编程题]游游的三色树
  • 热度指数：120 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
游游拿到了一棵树，其中每个节点被染成了红色（r）、绿色（g）或蓝色（b）。
游游想删掉一条边，使得剩下的两个连通块各恰好有三种颜色。
游游想知道，有多少合法的边可以删除？

注：树指不含重边和自环的无向连通图。

输入描述:
第一行输入一个正整数n，代表树的节点数量。
第二行输入一个长度为n的、仅包含'r'、'g'、'b'的字符串，第 i 个字符表示节点 i 的颜色。
接下来的 n-1行，每行输入两个正整数u和v，代表点u和点v有一条无向边连接。



输出描述:
合法的边的数量。
示例1

输入

7
rgbrgbg
1 2
2 3
3 4
4 5
5 6
6 7

输出

1

说明


如上图，只有删掉3-4这条边满足剩下两个连通块都有3种颜色。
算法知识视频讲解
添加回答
OfferLimitedExceeded头像 OfferLimitedExceeded
一开始以为是换根dp，结果其实是个比较简单的树上计数题。
假设树的根是id=1的那个节点，定义siz[i][j][k]表示第i个节点，考虑其子树上每个节点，颜色为j的节点之和，k=0代表其子树，k=1代表除了其子树以外的区域，siz[i][j][0]用dfs直接求，siz[i][j][1]实际就是拿根节点（即整棵树）的siz减去siz[i][j][0]，最后看是不是都>=1即可。
#include <iostream>
#include <string>
#include<vector>
#include<cstring>
using namespace std;
using ll = long long;
string s;
int n;
vector<int>g[100005];
ll siz[100005][3][2];
void dfs(int u, int fa){
    for(auto v : g[u]){
        if(v == fa){
            continue;
        }
        dfs(v,u);
        siz[u][0][0] += siz[v][0][0], siz[u][1][0] += siz[v][1][0], siz[u][2][0] += siz[v][2][0];
    }
}
void dfs2(int u, int fa){
    if(u != 1){
        siz[u][0][1] = siz[1][0][0]-siz[u][0][0];
        siz[u][1][1] = siz[1][1][0]-siz[u][1][0];
        siz[u][2][1] = siz[1][2][0]-siz[u][2][0];
    }
    for(auto v : g[u]){
        if(v == fa){
            continue;
        }
        dfs2(v,u);
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n;
    cin >> s;
    memset(siz,0,sizeof siz);
    for(int i = 1;i <= n;++i){
        if(s[i-1] == 'r'){
            siz[i][0][0]++;
        }
        else if(s[i-1] == 'g'){
            siz[i][1][0]++;
        }
        else{
            siz[i][2][0]++;
        }
    }
    for(int i = 1,u,v;i < n;++i){
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,0);
    dfs2(1,0);
    ll ans = 0;
    for(int i = 2;i <= n;++i){
        if(siz[i][0][0] >= 1 && siz[i][1][0] >= 1 && siz[i][2][0] >= 1 && siz[i][0][1] >= 1 && siz[i][1][1] >= 1 && siz[i][2][1] >= 1){
            ans++;
        }
    }
    cout << ans << "\n";
    return 0;
}
// 64 位输出请用 printf("%lld")


发表于 2023-10-20 16:30:27 回复(0)
C/C++
烦恼的伊泽瑞尔不讲武德头像 烦恼的伊泽瑞尔不讲武德
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 1e5 + 10, M = 2e5 + 10;

struct Edges
{
    int r, g, b;
};

int n;
int h[N], e[M], ne[M], idx;
char colors[N];
int sumr, sumg, sumb;
int ans = 0;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

Edges dfs(int u, int father)
{
    Edges local = {0, 0, 0};
    for (int i = h[u]; ~i; i = ne[i])
    {
        int son = e[i];
        if (son == father) continue;
        Edges tmp = {0, 0, 0};
        auto edges = dfs(son, u);
        tmp.r += edges.r;
        tmp.g += edges.g;
        tmp.b += edges.b;
        local.r += edges.r;
        local.g += edges.g;
        local.b += edges.b;
        if (tmp.r && tmp.g && tmp.b && sumr - tmp.r && sumg - tmp.g && sumb - tmp.b) ans ++;
    }
    if (colors[u] == 'r') local.r ++;
    else if (colors[u] == 'g') local.g ++;
    else local.b ++;
    return local;
}

int main()
{
    memset(h, -1, sizeof h);
    scanf("%d%s", &n, colors + 1);
    for (int i = 0; i < n - 1; i ++ )
    {
        int u, v;
        scanf("%d%d", &u, &v);
        add(u, v);
        add(v, u);
    }
    for (int i = 1; i <= n; i ++ )
        if (colors[i] == 'r') sumr ++;
        else if (colors[i] == 'g') sumg ++;
        else sumb ++;
    dfs(1, -1);
    printf("%d\n", ans);

    return 0;
}
发表于 2023-09-06 23:42:48 回复(0)
guluwulu头像 guluwulu

为啥过6/11？，预期21565，实际输出21566

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

bool track(unordered_map<int, vector<int>>& tree, string& color, int n1, int n2, int& r, int& g, int& b){
    if(color[n1 - 1] == 'r') r++;
    else if(color[n1 - 1] == 'g') g++;
    else b++;
    if(r&&g&&b) return true;
    bool rgb = false;

    for(int i = 0; i < tree[n1].size(); i++){
        if(tree[n1][i] == n2) continue;
        else{
            if(color[tree[n1][i] - 1] == 'r') r++;
            else if(color[tree[n1][i] - 1] == 'g') g++;
            else b++;
        }
        rgb |= track(tree, color, tree[n1][i], n1, r, g, b);
    }
    return rgb;
}

bool check(unordered_map<int, vector<int>>& tree, string& color,int n1, int n2){
    int r=0, g=0, b=0;
    return track(tree, color, n1, n2, r, g, b);
}

int main() {
    int n;
    while (cin >> n) { // 注意 while 处理多个 case
        string color;
        cin >> color;
        unordered_map<int, vector<int>> tree;        
        int f, c;
        vector<vector<int>> edge;
        for(int i = 0; i < n; i++){
            cin >> f >> c;
            edge.push_back({f, c});
            tree[f].push_back(c);
            tree[c].push_back(f);
        }
        int res = 0;
        for(int i = 0; i < edge.size(); i++){
            if(check(tree, color, edge[i][0], edge[i][1]) && check(tree, color, edge[i][1], edge[i][0])){
                res++;
            }
        }
        cout << res << endl;
    }
}
// 64 位输出请用 printf("%lld")
发表于 2023-09-02 21:39:30 回复(0)
提交观点

问题信息

来自：2022年携程秋招第一批
难度：
3条回答 978浏览

热门推荐

相关试题

游游的三色树

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号