Дорешивая эту задачу я практически не понимаю ее разбор.
Единственное, что я понял это:
Можете помочь с решением?
Я решал эту задачу по другому.
Подвесим оба дерева за вершину 1.
Когда мы считаем ответ для вершины v, давайте заметим что размер поддеревьев изменяется только на пути между 1 и v. Как изменяется размер на пути? Пусть r[u] - вершина которая идет после u на пути от 1 до v, тогда после подвешивания за v размер поддерева u станет n - sz[r[u]] где sz[r[u]] размер поддерева в изначальном дереве.
Можно заметить что возможных размеров поддерева u будет очень много, но мы обойдем этот шаг одним нехитрым движением, давайте построим HLD на втором дереве, теперь для почти всех вершин на пути от 1 до v мы знаем размер при переподвешивании за v, а вершин для которых мы не знаем будет всего \log(n). Внутри каждого бамбука будет только одна вершина у которой следующая вершина не будет внутри этого же бамбука, всего на пути \leq \log(n) бамбуков.
Давайте в первом дереве проходиться с помощью обхода в глубину, а во втором дереве считать что размеры вообще не меняются, тогда мы легко сможем посчитать ans', а как посчитать настоящий ответ? Для \log(n) вершин для которых следующий находится вне бамбука мы считаем изменение вручную, внутри бамбуков мы можем брать сумму на отрезке, для каждой вершины посчитаем изменение если вершина станет n - sz[r[u]] и закинем все эти значения в структуру. Так как в первом дереве размеры поддеревьев “константны” на момент подсчета ответа для вершины v то все будет очень просто, в итоге это работает за O(N\log^2(N))
что такое ans'?
Давайте в первом дереве проходиться с помощью обхода в глубину, а во втором дереве считать что размеры вообще не меняются
Ответ если бы второе дерево имело зафиксированные размеры поддеревьев (Изначальные).
а как?
внутри бамбуков мы можем брать сумму на отрезке, для каждой вершины посчитаем изменение если вершина станет n−sz[r[u]] и закинем все эти значения в структуру.
и как мы будем сумму на отрезке брать, если мы никак это не можем связать с значения вершин бамбука в первом дереве?
Размер вершинв переподвешенном дереве на пути от 1 до v зависит от следующей вершины на пути, в хлд если мы не на краю то мы однозначно знаем следующую вершину на пути, так как такая вершина только одна