На каждый запрос можно отвечать за O(n). Когда пришел запрос — будем проверять все поддеревья того же размера, что и дерево в запросе. Проверять поддерево будем втупую проходясь по нему целиком. Понятно, что каждая вершина будет принадлежать не более, чем одному из таких поддеревьев.

При данных ограничениях O(nq) — это 2·10⁷, что должно спокойно проходить.

Я не знаю как то условие переводить, чтобы оно было читаемое и понимаемое. Кстати, переводчик на китайский тоже был назначен, но в последний момент куда-то пропал :)

Вообще говоря, про то, что нельзя переставлять местами сыновей, можно было в силу того, что иначе непонятно, зачем эти метки на ребрах. Хотя, конечно же, условия ужасные были. Есть информация, что этот автор не будет впредь допущен к подготовке контестов, по крайней мере ланчей и куков.

Решается и за NlogN очень просто. Если под недетерминированным решением имеются в виду хеши, то детерминированное решение пишется проще них. Сделаем обход в глубину и каждой вершине присвоим класс эквивалентности поддерева. Для этого будем хранить глобальную мапу из тройки (age, класс левого ребенка, класс правого ребенка) в класс. Если какого-то ребенка нет, будем для удобства считать, что его класс -1. В обходе найдя классы двух детей, посмотрим, есть ли тройка в мапе, и если нет — создадим. Обойдем исходное дерево, получим заполненную мапу. Теперь с той же мапой обойдем каждое дерево-запрос, но запретим добавлять в нее новые элементы. Если захотелось добавить новый элемент, вываливаемся и отвечаем на запрос "нет".