#include <bits/stdc++.h>
#include "beechtree.h"
using namespace std;
using ll = long long;
const int mxN = 2e5+10;
int c[mxN];
vector<int> adj[mxN];
bool pos[mxN];
array<int, 2> cont[mxN];
set<int> dfs(int node, int p) {
set<int> colors, all_colors;
int cont_cnt = 0;
vector<set<int>> v;
for(auto it : adj[node]) {
if(it == p) continue;
if(colors.count(c[it]) != 0) {
pos[node] = false; break;
}
all_colors.insert(c[it]);
colors.insert(c[it]);
set<int> nxt_colors = dfs(it, node);
if(!pos[it]) {
pos[node] = false; break;
}
v.push_back(nxt_colors);
if(cont[it][0] >= 2) {
++cont_cnt;
if(cont[it][1] != c[it]) pos[node] = false;
}
if(nxt_colors.size() > all_colors.size()) swap(nxt_colors, all_colors);
for(auto it : nxt_colors) {
all_colors.insert(it);
}
}
for(auto it : adj[node]) {
if(it == p) continue;
if(cont[it][0] + 1 > cont[node][0]) {
if(cont[it][0] < 2 || (cont[it][0] >= 2 && cont[it][1] == c[it])) {
cont[node][0] = cont[it][0] + 1;
cont[node][1] = c[it];
}
}
}
if(cont_cnt > 1) pos[node] = false;
for(auto it : all_colors) {
if(!colors.count(it)) {
pos[node] = false; break;
}
}
if(!pos[node]) return {};
sort(v.begin(), v.end(), [&](set<int> a, set<int> b) {
return a.size() > b.size();
});
for(int i = 1; i < v.size(); i++) {
for(auto it : v[i]) {
int it1 = v[i-1].count(it);
if(it1 == 0) {
pos[node] = false;
break;
}
}
}
if(pos[node]) return all_colors;
else return {};
}
vector<int> beechtree(int n, int m, vector<int> p, vector<int> C) {
for(int i = 1; i < n; i++) {
adj[i].push_back(p[i]);
adj[p[i]].push_back(i);
c[i] = C[i];
pos[i] = true;
}
pos[0] = true;
dfs(0, -1);
vector<int> ans(n);
for(int i = 0; i < n; i++) ans[i] = pos[i];
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |