Блог пользователя Mehrdad_Sohrabi

Hmmmmm
Автор Mehrdad_Sohrabi, 5 лет назад, По-английски

Hi :)

Suppose whe have a tree that each vertex has a value

we have two types of query

1 : changing value of a vertex

2 : print the minimum value in the path of u and v

Do you have answer without hld

  • Проголосовать: нравится
  • -38
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Get sqrt(n) special vertices so that at maximum of sqrt(n) level ahead of it is a special vertex by using bfs from leaf. On each special vertex store minimum value from that vertex to its special ancestor in a multiset. Update by update new value for every special vertex possible as it should be only sqrt(n) special vertices at most, and you can aid finding valid special vertice to update with lca. Every query should cost sqrt(n)log(n).

→ Ответить