題目鏈接
RGB樹-美團2023筆試(codefun2000)

題目內容

塔子哥是一位著名的冒險家，他經常在各種森林里探險。今天，他來到了道成林，這是一片美麗而神秘的森林。在探險途中，他遇到了一棵 n 個節點的樹，樹上每個節點都被涂上了紅、綠、藍三種顏色之一。塔子哥發現，如果這棵樹同時存在一個紅色節點、一個綠色節點和一個藍色節點，那么我們就稱這棵樹是多彩的。很幸運，他發現這棵樹最初就是多彩的。但是，在探險的過程中，塔子哥發現這棵樹上有一條邊非常重要，如果砍掉這條邊，就可以把這棵樹分成兩個部分。他想知道，有多少種砍法可以砍掉這條邊，使得砍完之后形成的兩棵樹都是多彩的。

輸入描述

第一行個整數 n ，表示節點個數
第二行n?1 個整數 𝑝2，𝑝3,…,𝑝𝑛，pi表示樹上 i 和 𝑝 兩點之間有一條邊。保證給出的定是一棵樹。
第三行一個長度為 n 的字符串，第 i 個字符表示第 i 個節點的初始顏色。其中 R 表示紅色， G 表示綠色， B 表示藍色。
保證字符串只由這三種大寫字母構成對于全部數據， $3\le n\le 10^5$。

輸出描述

輸出一行，一個正整數，表示答案。

樣例1

輸入

7
1 2 3 1 5 5
GBGRRBB

輸出

1

題解1

#include<bits/stdc++.h>
using namespace std;const int N = 1e5 + 10;int n, ans;
struct Node{int Rcnt,Gcnt,Bcnt;
}node[N];
char s[N];
vector<int> edge[N];void dfs1(int u){ // 統計以u為根節點的顏色為RGB的節點個數int sz = edge[u].size();if(sz == 0) return ;for(int i = 0; i < sz; i++){int v = edge[u][i];dfs1(v);node[u].Rcnt += node[v].Rcnt;node[u].Gcnt += node[v].Gcnt;node[u].Bcnt += node[v].Bcnt;}
}
void dfs2(int u){int sz = edge[u].size();for(int i = 0; i < sz; i++){ // 遍歷每條邊，以每條邊為邊界，分成兩部分，判斷兩部分的RGB顏色節點個數是否>=1 int v = edge[u][i];int rcnt = node[v].Rcnt;int gcnt = node[v].Gcnt;int bcnt = node[v].Bcnt;int Rcnt = node[1].Rcnt - rcnt;int Gcnt = node[1].Gcnt - gcnt;int Bcnt = node[1].Bcnt - bcnt;if(rcnt >= 1 && gcnt >= 1 && bcnt >= 1 && Rcnt >= 1 && Gcnt >= 1 && Bcnt >= 1) {ans++;dfs2(v);}}
} 
int main(){scanf("%d", &n);for(int i = 2, u; i <= n; i++){scanf("%d", &u);edge[u].push_back(i);}scanf("%s", s + 1);for(int i = 1; s[i] != '\0'; i++){if(s[i] == 'G') node[i].Gcnt++;else if(s[i] == 'R') node[i].Rcnt++;else if(s[i] == 'B') node[i].Bcnt++;}dfs1(1);dfs2(1);printf("%d\n", ans); return 0;
}