#include #include #include #include using namespace std; class Node{ public: int value; bool is_leaf = true; Node* left = nullptr; Node* right = nullptr; Node* parent = nullptr; Node(int a) : value(a), is_leaf(true), left(nullptr), right(nullptr), parent(nullptr) {}; }; class Graph{ public: Node* root = nullptr; Graph(int a) { root = new Node(a); } Node* traverse(Node* current, int value) { if (current == nullptr) return nullptr; if (current->value == value) return current; Node* found = traverse(current->left, value); if (found) return found; return traverse(current->right, value); } void insert(int value, int parent) { Node* parents = traverse(root, parent); if (parents == nullptr) return; Node* now = new Node(value); now->parent = parents; if (parents->left == nullptr) parents->left = now; else if (parents->right == nullptr) parents->right = now; parents->is_leaf = false; } void remove_subtree(Node* current) { if (current == nullptr) return; remove_subtree(current->left); remove_subtree(current->right); if (current->parent != nullptr) { if (current->parent->left == current) current->parent->left = nullptr; else if (current->parent->right == current) current->parent->right = nullptr; if (current->parent->left == nullptr && current->parent->right == nullptr) current->parent->is_leaf = true; } } void find_leaf(Node* current, int& count) { if (current == nullptr) return; if (current->is_leaf) count += 1; else { find_leaf(current->left, count); find_leaf(current->right, count); } } }; int main() { int N; cin >> N; vector parents(N); Graph* graph = nullptr; for (int i = 0; i < N; i++) cin >> parents[i]; for (int i = 0; i < N; i++) { if (parents[i] == -1) { graph = new Graph(i); break; } } for (int i = 0; i < N; i++) { if (parents[i] != -1) graph->insert(i, parents[i]); } int remove; cin >> remove; if (remove == graph->root->value) { cout << 0 << "\n"; return 0; } Node* target = graph->traverse(graph->root, remove); graph->remove_subtree(target); int number = 0; graph->find_leaf(graph->root, number); cout << number << "\n"; return 0; }

제출 #58880

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: