Задача состоит в проверке, имеет ли первое дерево подграф, изоморфный второму дереву. Давайте попробуем решить задачу с любой асимптотикой, а затем уберем все лишнее из решения.
Сделаем первое дерево корневым и решим задачу с помощью динамического программирования на его поддеревьях. Пусть $$$\mathtt{dp}[u][x \to v]$$$, где $$$u$$$ — вершина первого дерева, а $$$x \to v$$$ — ориентированное ребро второго дерева, будет означать, возможно ли сопоставить вершины $$$u$$$ и $$$v$$$, при этом
Для подсчета такой динамики нам нужны значения всех $$$\mathtt{dp}[u'][v \to v']$$$, где $$$u'$$$ — сын $$$u$$$, а $$$v'$$$ — сын $$$v$$$. Сам пересчет является проверкой, есть ли паросочетание в двудольном графе, которое покрывает левую часть — действительно, поддеревья каких-то детей $$$u$$$ надо «покрыть» поддеревьями детей $$$v$$$, а всех остальных — добавить отдельно.
К сожалению, такая динамика работает очень медленно и не дает ответа на задачу. Давайте исправим обе эти проблемы сразу. Посмотрим на пересчет всех состояний динамики вида $$$\mathtt{dp}[u][x \to v]$$$ для разных $$$x$$$. Для их пересчета мы ищем совпадение для графов с одинаковой правой частью (все дети $$$u$$$) и левой частью, которая отличается одной вершиной (все соседи $$$v$$$, кроме $$$x$$$).
Вместо этого давайте сразу запустим поиск паросочетания на графе со всеми интересующими нам вершинами, то есть только один раз для пары вершин $$$u$$$ и $$$v$$$. Тогда:
Решение заканчивается здесь, для ответа остается только рассмотреть какой-то лист в качестве $$$x$$$ и найти, есть ли соответствующий $$$\mathtt{dp}$$$, равный true.
Остается только оценить его время выполнения — мы запускаем один алгоритм поиска паросочетания для каждой пары вершин $$$(u, v)$$$. Давайте посчитаем максимально возможное количество ребер во всех полученных графах, то есть $$$\sum\limits_{u, v} \mathrm{deg}(u) \cdot \mathrm{deg}(v) = \sum\limits_{u}{\mathrm{deg}(u) \cdot 2 \cdot m} = 4 n m$$$.
Если честно оценить алгоритм Куна, то мы получим асимптотику всего решения $$$\mathcal{O}(n m^2)$$$, однако на конкретных графах алгоритм Куна на самом деле работает гораздо быстрее, поэтому такое решение уже проходит при достаточно аккуратной реализации. Если вы действительно хотите написать асимптотически более быстрое решение, напишите алгоритм Диница, чтобы получить решение за $$$\mathcal{O}(n m \sqrt{m})$$$.