Mehrdad_Sohrabi's blog

Hmmmmm
By Mehrdad_Sohrabi, 5 years ago, In English

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

  • Vote: I like it
  • -38
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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).

→ Reply