Формулировка задачи
Нам дано дерево с вершинами, и нужно обработать запросов.
Каждый запрос задаёт множество вершин
Нам дано дерево с вершинами, и нужно обработать запросов.
Каждый запрос задаёт множество вершин
Для этого множества нужно вычислить сумму расстояний по всем парам выбранных вершин:
где — расстояние, то есть количество рёбер на пути между и .
Если в запрос включены все вершины дерева, то задача становится намного проще.
Мы можем вычислить вклад каждого ребра независимо и добавить все вклады к ответу.
Это приводит к решению за .
Эта идея также работает для взвешенных деревьев.
В общем случае мы не хотим обрабатывать всё дерево для каждого запроса.
Вместо этого мы строим виртуальное дерево (также называемое вспомогательным деревом) для запрошенных вершин и сводим задачу к гораздо меньшему дереву.
Дано множество вершин
виртуальное дерево — это минимальное множество вершин
такое, что замкнуто относительно операции LCA.
Это означает:
То есть виртуальное дерево состоит только из:
Это делает его намного меньше исходного дерева.
В качестве примера рассмотрим следующее дерево с вершинами и предположим, что мы хотим построить виртуальное дерево для множества
Чтобы построить виртуальное дерево для множества :
Построение со стеком работает, потому что вершины обрабатываются в порядке DFS.
Суммарная сложность построения виртуального дерева:
при условии, что запросы LCA уже доступны.
void VirtualTree(vector<int> v) {
// sort by DFS entry time
sort(v.begin(), v.end(), [&](int x, int y) {
return tin[x] < tin[y];
});
vector<int> s = v;
for (int i = 1; i < (int)v.size(); i++) {
s.push_back(lca(v[i], v[i - 1]));
}
sort(s.begin(), s.end(), [&](int x, int y) {
return tin[x] < tin[y];
});
s.erase(unique(s.begin(), s.end()), s.end()); // remove duplicates
// s[0] is the root of the virtual tree
vector<int> st = {s[0]};
for (int i = 1; i < (int)s.size(); i++) {
while (!st.empty() && !is_parent(st.back(), s[i])) {
st.pop_back();
}
add_edge(st.back(), s[i]);
st.push_back(s[i]);
}
}