Блог пользователя Amiya-05

Автор Amiya-05, история, 2 месяца назад, По-английски

Hello! I have come across a tree problem where number of nodes(V<=1e5) and number of edges(E<=1e5) and edge weights are given .There are Q (Q<=1e5) queries of two types:

Query 1 asks to change the weight of edge i to W (given in query) Query 2 asks to print the path length between nodes a and b (given in query)

//As I know, LCA can be used to find the distance when edge weights are not changing (But does not seem to be useful here)

Can anyone suggest any method on how to solve it efficiently ?

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

»
2 месяца назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Using heavy-light decomposition should be ok

»
2 месяца назад, # |
  Проголосовать: нравится +54 Проголосовать: не нравится

Instead of doing HLD, you can do Euler Tour Tree+fenwick, which will work faster and will be much easier to write

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    How on a path? I can see it on subtree not a path

    • »
      »
      »
      2 месяца назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Let F[u] be the sum of the weights of edges going from u to the root node

      then an update to the edge connecting node k and it's parent would change all F[v] where v is in subtree k

      with euler tour, all the v values are going to be in a range [l..r]

      to calculate distance, it's just: F[u] + F[v] — F[lca(u,v)]

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Okay I will explore that too. Thanks !

»
2 месяца назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

sqrt decomposition (keep lazy updates and rebuild distance after each B queries)

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can't u flat the tree? the LCA with rmq in O(1), use the same logic but have a segment tree and handle edge changing withing the segment, I believe it should be fine

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

maybe sqrt decomposition will work

»
2 месяца назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Simply change the query to the root to the vertex $$$a$$$. Then you can use DFS index and fenwick tree to solve this in $$$O(n \log n)$$$ time, which is fast enough.

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Detaily, let $$$id_u$$$ be the DFS id of vertex $$$u$$$, and $$$sz_u$$$ denotes the size of the subtree rooted at vertex $$$u$$$. Note that a subtree rooted at $$$u$$$ is $$$[id_u, id_u+sz_u-1]$$$, so in fact you need to solve segment add and single point query. Use fenwick tree to solve it!