# 12183 - Fairy Testing
>author: Utin
###### tags: `binary tree`
---

## Brief
See the code below

## Solution 0 (Malloc Version)

#include <stdio.h>
#include <stdlib.h>

typedef enum _type {
    AND, OR, NUM
} Type;

typedef struct _node {
    int value;
    Type id;
    struct _node* left, * right, * parent;
} Node;

int T, N, M, tmp_ans;
Node* Root;
Node* arr[100005];

Node* make_node(int data, Node* parent, Type type);
Node* create_tree(Node* parent);
int count(Node* node);
void flip(Node* node);
void destroy(Node* node);

int main() {
    scanf("%d", &T);
    while (T--) {
        tmp_ans = 0;
        scanf("%d %d", &N, &M);
        Root = create_tree(NULL);
        while (M--) {
            int id;
            scanf("%d", &id);
            flip(arr[id]);
            printf("%d\n", count(arr[id]));
        }
        destroy(Root);
    }
}

Node* make_node(int data, Node* parent, Type type) {
    Node* new_node = (Node*) malloc(sizeof(Node));
    new_node->value = 0;
    new_node->id = type;
    new_node->parent = parent;
    new_node->left = NULL;
    new_node->right = NULL;
    if (type == NUM) arr[data] = new_node;
    return new_node;
}

Node* create_tree(Node* parent) {
    char input;
    int data;
    Type type;
    scanf(" %c", &input);
    if (input == '[') {
        int id;
        scanf("%d]", &id); // 會有10位數以上
        data = id;
        type = NUM;
    }
    else {
        data = input;
        type = input == '&' ? AND : OR;
    }

    // create node
    Node* new_node = make_node(data, parent, type);

    // operator has leftchild and rightchild
    if (type != NUM) {
        new_node->left = create_tree(new_node);
        new_node->right = create_tree(new_node);
    }

    return new_node;
}

int count(Node* node) {
    if (!node->parent) return tmp_ans = node->value;

    else if (node->parent->id == OR) {
        int tmp = node->parent->left->value | node->parent->right->value;
        if (tmp == node->parent->value) return tmp_ans;
        else node->parent->value = tmp;
    }

    else if (node->parent->id == AND) {
        int tmp = node->parent->left->value & node->parent->right->value;
        if (tmp == node->parent->value) return tmp_ans;
        else node->parent->value = tmp;
    }

    return count(node->parent);
}

void flip(Node* node) {
    node->value = node->value ? 0 : 1;
}

void destroy(Node* node) {
    if (node->left) destroy(node->left);
    if (node->right) destroy(node->right);
    free(node);
}

// Utin

## Solution 1 (Without Malloc Version)

#include <stdio.h>

typedef enum _type {
    AND, OR, NUM
} Type;

typedef struct _node {
    int value;
    Type id;
    struct _node* left, * right, * parent;
} Node;

int T, N, M, tmp_ans, pos;
Node* Root;
Node* arr[100005];
Node hole[200005];

Node* make_node(int data, Node* parent, Type type);
Node* create_tree(Node* parent);
int count(Node* node);
void flip(Node* node);
void destroy(Node* node);

int main() {
    scanf("%d", &T);
    while (T--) {
        tmp_ans = 0;
        scanf("%d %d", &N, &M);
        pos = 0;
        Root = create_tree(NULL);
        while (M--) {
            int id;
            scanf("%d", &id);
            flip(arr[id]);
            printf("%d\n", count(arr[id]));
        }
        // destroy(Root);
    }
}

Node* make_node(int data, Node* parent, Type type) {
    Node* new_node = &hole[pos++];
    new_node->value = 0;
    new_node->id = type;
    new_node->parent = parent;
    new_node->left = NULL;
    new_node->right = NULL;
    if (type == NUM) arr[data] = new_node;
    return new_node;
}

Node* create_tree(Node* parent) {
    char input;
    int data;
    Type type;
    scanf(" %c", &input);
    if (input == '[') {
        int id;
        scanf("%d]", &id); // 會有10位數以上
        data = id;
        type = NUM;
    }
    else {
        data = input;
        type = input == '&' ? AND : OR;
    }

    // create node
    Node* new_node = make_node(data, parent, type);

    // operator has leftchild and rightchild
    if (type != NUM) {
        new_node->left = create_tree(new_node);
        new_node->right = create_tree(new_node);
    }

    return new_node;
}

int count(Node* node) {
    if (!node->parent) return tmp_ans = node->value;

    else if (node->parent->id == OR) {
        int tmp = node->parent->left->value | node->parent->right->value;
        if (tmp == node->parent->value) return tmp_ans;
        else node->parent->value = tmp;
    }

    else if (node->parent->id == AND) {
        int tmp = node->parent->left->value & node->parent->right->value;
        if (tmp == node->parent->value) return tmp_ans;
        else node->parent->value = tmp;
    }

    return count(node->parent);
}

void flip(Node* node) {
    node->value = node->value ? 0 : 1;
}

// Utin

## Reference