Виртуальное дерево / Вспомогательное дерево
Дано дерево с вершинами. Обработайте запросов вида . Для каждого запроса выведите сумму расстояний для каждой пары из заданного множества вершин. Более формально, найдите
где — расстояние (число рёбер) между вершинами и .
По сути, все вершины включены в множество.
Решение довольно простое: найти вклад каждого ребра и добавить его к ответу. Сложность .
Примечание: это также работает для взвешенных рёбер, если использовать веса рёбер вместо .
Для общего случая мы вводим Виртуальное дерево (Вспомогательное дерево) и сводим задачу к частному случаю на гораздо меньшем дереве.
Виртуальное дерево для заданного множества — это минимальное множество вершин , такое что:
Это означает, что для любых двух вершин также выполняется .
В качестве примера рассмотрим следующее дерево с вершинами и предположим, что мы хотим построить виртуальное дерево для множества .
Чтобы построить Вспомогательное дерево, соответствующее множеству :
tin).lca в множество.Это даёт минимальное множество, замкнутое относительно LCA, и мы можем построить виртуальное дерево с общей сложностью .
После построения виртуального дерева мы решаем запрос, используя вклады рёбер.
Для ребра виртуального дерева :
Тогда это ребро вносит вклад в сумму по неупорядоченным парам:
Поскольку задача спрашивает про упорядоченные пары (и , и ), умножаем на :
Значит, нам нужен только один DFS по виртуальному дереву, чтобы посчитать все количества в поддеревьях и накопить ответ.
Это сохраняет общую сложность на запрос на уровне:
void VirtualTree(vector<int> v) {
// sort by DFS traversal order
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()); // delete duplicates
// build edges of the virtual tree using stack
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]);
}
}