游游拿到了一棵树,其中每个节点被染成了红色(r)、绿色(g)或蓝色(b)。
游游想删掉一条边,使得剩下的两个连通块各恰好有三种颜色。
游游想知道,有多少合法的边可以删除?
注:树指不含重边和自环的无向连通图。
第一行输入一个正整数,代表树的节点数量。
第二行输入一个长度为的、仅包含'r'、'g'、'b'的字符串,第 个字符表示节点 的颜色。
接下来的 行,每行输入两个正整数和,代表点和点有一条无向边连接。
合法的边的数量。
7 rgbrgbg 1 2 2 3 3 4 4 5 5 6 6 7
1
如上图,只有删掉3-4这条边满足剩下两个连通块都有3种颜色。
#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")
#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")