Дано дерево с N вершинами, каждое ребро которого имеет вес 1. Узлы окрашены в C цвета. Мы хотим найти для каждого цвета максимальное кратчайшее расстояние между двумя узлами этого цвета.
Я могу построить разреженную таблицу, а затем найти LCA двух узлов в O(log n). Затем проверьте все пары одного цвета. Это дает O(n^2 log n). Можно ли сделать лучше, чем это?
Вы можете правильно манипулировать ребрами и запускать рекурсивный обход, начиная с каждого узла, как если бы он был корнем. Поскольку дерево имеет N узлов, N обходов даст вам O (N 2). жонглирование краями также должно занять O (n) времени, так как в дереве имеется (n-1) ребер. Если вы сохраните матрицу M с C строками и C столбцами и обновите ее при каждом обходе, то вы сможете делать то, что хотите, за O (N 2) за все время и космическая сложность.
В основном то, что вы делаете, будет обновлять c u th строку M в обходе, начиная с узла U с цветом c u следующим образом когда вы достигнете узла V с цветом c v на расстоянии d.
M[cu][cv] = max(M[cu][cv], d)
