Пускай дано корневое дерево, запустим dfs и будем выписывать все вершины которые мы посетим. Полученную строку назовем эйлеровым обходом дерева.
Заметим, что поддерево какой-либо вершины, является непрерывным отрезком эйлерового обхода. Будем поддерживать счетчик - сколько вершин уже посетили и для каждой вершины запомним значение счетчика, когда мы в нее зашли и когда вышли. Назовем эти два параметра \(tin_u\) и \(tout_u\) соответственно.
vector< int > euler;
int tin[n], tout[n];
int timer=-1;
void dfs(int w) {
euler.push_back(w);
tin[w] = ++timer;
for(auto to : tree[w])
dfs(to);
// в зависимости от реализации мы можем приписывать вершину
// когда выходим из вершины, и когда выходим из ее ребенка
tout[w] = timer;
}
Заметим, что если взять все вершины эйлерового обхода на отрезке \( [tin_u, tin_v] \), встречающиеся нечетное число раз, то все эти вершины будут лежать на пути между \(u\) и \(v\). Тогда мы можем свести все запросы на пути к запросам на отрезке. Таким образом работает Мо на дереве .
Так как поддерево вершины \(v\) представляется отрезком \( [tin_v; tout_v] \), то мы можем построить структуру на отрезке и поддерживать любые запросы на поддеревьях, которые умеем поддерживать на отрезке.
Если в dfs заходить сначала в самого тяжелого ребенка (имеющего самое большое поддерево), то "тяжелые" пути будут представлены подотрезками в эйлеровом обходе.
Если мы умеем вырезать подотрезки и вставлять их (например, с помощью декартового дерева), то мы сможем поддерживать операции удаления ребра в дереве.