Мне нужна помощь в решении этой проблемы.
У нас есть D(G,u,v) - число ребер на кратчайшем пути от u до v в графе G.
Мыдано дерево T с N вершинами и Q запросами следующего типа:
Если мы добавим ребро (a,b) к дереву T, получив граф G1, то чтозначение sum(1 <=u < v <= N) D(G1,u,v)
Запросы независимы
1<=N<=260000
1<=Q<=200000
D(T,a,b)<=16
Для каждого запроса я вызывал BFS для каждого узла и вычислял сумму расстояний, но мой алгоритм был медленным.Может кто-нибудь дать мне более эффективный подход?