qwerty787788's blog

By qwerty787788, 9 years ago, In Russian

Всем привет!

Может кто-нибудь где-нибудь видел задачу, в которой нужно поддерживать лес деревьев и делать на нем какие-то операции? Например, задача в которой требуется поддерживать следующие операции:

  • Подвесить одно дерево к вершине другого

  • Удалить ребро

  • Сказать, находятся ли две вершины в одном дереве (или какой-нибудь другой запрос)

Может кто-нибудь знает, как можно решать такую задачу, кроме как с помощью link-cut tree или хранения обходов деревьев в декартовых деревьях?

Буду очень благодарен за ссылки на задачи и мысли по поводу того, как проще всего такое решать!

  • Vote: I like it
  • +13
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +20 Vote: I do not like it