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

typedef struct tree {
    int is_branch;
    int x;
    struct tree *left;
    struct tree *right;
} tree;

long x = 10;

int rand() {
    x = (x * 27527 + 27791) % 41231;
    return x;
}

tree *make_tree(int max, int depth) {
    struct tree *p = malloc(sizeof(*p));
    if (depth <= 1) {
        p->is_branch = false;
    } else {
        p->is_branch = true;
        p->x = rand() % max;
        p->left = make_tree(max, depth - 1);
        p->right = make_tree(max, depth - 1);
    }
    return p;
}

bool is_sub(tree *a, tree *b) {
    if (!a->is_branch) return true;
    if (a->is_branch && b->is_branch) {
        if (a->x == b->x && is_sub(a->left, b->left) && is_sub(a->right, b->right)) {
            return true;
        } else {
            return (is_sub(a, b->left) || is_sub(a, b->right));
        }
    }
    return false;
}

int count_subtrees(tree *a, tree *b) {
    if (!a->is_branch) return 1;
    return is_sub(a,b) + count_subtrees(a->left, b) + count_subtrees(a->right, b);
}

int main() {
    tree *t = make_tree(10, 19);
    tree *f = make_tree(9, 19);
    clock_t begin = clock();

    int res = count_subtrees(f, t);

    clock_t end = clock();
    double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
    printf("count: %d time: %lf\n", res, time_spent);
}