Продолжение истории про центроидную декомпозицию
Задача: Дерево с длинами у рёбер, реализовать структуру данных, которая позволяет быстро выполнять две операции: находить длину пути между двумя вершинами и изменять длину ребра.
Структура данных, которая позволяет выполнять оба запроса со стоимостью O(sqrt(n))
Дерево подвешено за нулевую вершину: int[] parent = new int[N]; int[] edgeLenght = new int[N]; //*
Часть вершин покрашено в белый Set whites = new HashSet(); так, что выполнены следующие условия:
- Корень белый
- Белых вершин O(sqrt(n))
- При удаленни белых вершин дерево распадается на компоненты связности, при этом максимальный размер компоненты связности тоже O(sqrt(N))
Хозяином белой вершины назовём её саму, а хозяином чёрной - ближайшего её белого предка. Для каждой вершины храним её хозяина и расстояние до хозяина:
int[] master = new int[N]; int[] lengthToMaster = new int[N]; //*
Для каждой чёрной вершины храним список её чёрных детей в первом поколении: List<Set> children = new ArrayList<>();
Ещё нужна структура данных, которая по паре вершин быстро вычисляет их ближайшего общего предка int lca(int first, int second); // реализаций с асимптотикой O(log(N)) много, тут писать лень.
Теперь можно реализовать требуемый интерфейс void changeLen(int from, int to, int len){ if(parent[from] == to) changeLen(from, len); else if (parent[to] == from) changeLen(to, len); else throw new RuntimeException("Unknown edge"); }
Из хранимых данных при смене длины ребра нужно пересчитать только edgeLength и, если нижняя вершина чёрная, lenghtToMaster, причём только для её потомков внутри той компоненты связности, в которой окажется вершина при удалении белых вершин, так что стоимость операции в худшем случае O(sqrt(N))
void changeLen(int down, int len){ if(!whites.contains(down)){ changeLenToMaster(down, len - lenghtToMaster[down]); } edgeLenght[down] = len; }
void changeLenToMaster(int v, int d){ lenghtToMaster[v] +=d; for(int i: children.get(v) ) changeLenToMaster(i, d); }
Вычисление длины пути:
Случай, когда вторая вершина является потомком первой: int findLenToParent(int a, int p){ if(master[a] == master[p]) return lenghtToMaster[a] - lenghtToMaster[p]; return lenghtToMaster[a] + edgeLenght[master[a]] + findLenToParent(parent[master[a]], p); } (Можно переписать нерекурсивно) на каждом рекурсивном вызове нижняя вершина меняет мастера, мастеров у нас всего O(sqrt(N)), причём очевидно, что второй раз к тому же мастеру она не попадёт, отсюда стоимость операции - O(sqrt(N)) в худшем случае.
Общий случай int findLen(int a, int b){ int p = lca(a, b); return findLenToParent(a, p) + findLenToParent(b, p); }
Осталось построить эту самую структуру данных, имея начальное состояние дерева. Единственное нетривиальное - выбор белых вершин, делается как раз при помощи центроидной декомпозиции. Выбираем некое пороговое значение M ~ sqrt(N), запускаемся рекурсивно от всего дерева - если его размер больше M - добавляем центроид в белое множество и запускаемся рекурсивно от оставшихся поддеревьев.
Довольно просто доказать, что итоге белых вершин будет не более 2*N/M ~ sqrt(N), остаётся добавить в белые корень.