Untitled

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 2000000

typedef struct node{
    int value; // This is the value of the subtree, not the ID number
    int tokentype;
    struct node *leftchild;
    struct node *rightchild;
    struct node *parent; //pointing to the parent node
}Node;

Node* variable[100001];
char s[MAX];
int pos = 0;

Node* makeNode(){
    Node* nd = (Node*)malloc(sizeof(Node));
    int i = pos, num = 0;
    while(s[i] != ']')
        i++;
    for(int j = pos; j < i; j++)
        num = num*10 + s[j] - '0';
    variable[num] = nd;
    pos = i;
    nd->value = 0;
    nd->tokentype = 0; //是變數的話 tokentype = 0
    nd->leftchild = NULL, nd->rightchild = NULL, nd->parent = NULL;
    return nd;
}

Node* makeOper(){
    Node* nd = (Node*)malloc(sizeof(Node));
    nd->rightchild = NULL, nd->leftchild = NULL, nd->parent = NULL;
    nd->value = 0;
    if(s[pos] == '|') nd->tokentype = 1; // 是or的話 tokentype = 1
    else if(s[pos] == '&') nd->tokentype = 2; // 是and的話 tokentype = 2
    return nd;
}

void freeTree(Node* head){
    if(head != NULL){
        freeTree(head->leftchild);
        freeTree(head->rightchild);
        free(head);
    }
    return;
}

Node* createTree(){
    Node* nd = NULL;
    if(pos < strlen(s)){
        if(s[pos] == '|' || s[pos] == '&'){
            nd = makeOper();
            pos++;
            nd->leftchild = createTree();
            nd->leftchild->parent = nd;
            pos++;
            nd->rightchild = createTree();
            nd->rightchild->parent = nd;
        }
        else if(s[pos] == '['){
            pos++;
            nd = makeNode();
        }
        return nd;
    }
    return nd;
}

void flip(int n){
    Node* nd = variable[n];
    if(nd->value == 1) nd->value = 0;
    else nd->value = 1;
}

void check(Node* nd){
    if(nd->parent == NULL) return; 
    Node* pa = nd->parent;
    int changed = pa->value;
    if(pa->tokentype == 1){
        if(pa->leftchild->value == 1 || pa->rightchild->value == 1)
            pa->value = 1;
        else
            pa->value = 0;
    }
    else if(pa->tokentype == 2){
        if(pa->leftchild->value == 1 && pa->rightchild->value == 1)
            pa->value = 1;
        else
            pa->value = 0;
    }
    if(changed != pa->value) check(pa);
    return;
}

int main(){
    int t;
    scanf("%d", &t);
    while(t--){
        int n, m;
        pos = 0;
        memset(s, '\0', sizeof(s));
        scanf("%d%d%s", &n, &m, s);
        Node* head = createTree();
        for(int i = 0; i < m; i++){
            int f;
            scanf("%d", &f);
            flip(f);
            check(variable[f]);
            printf("%d\n", head->value);
        }
        freeTree(head);
    }
}