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

Need help with tree problem
Автор I_love_Vovuh_s_cat, история, 6 лет назад, По-английски

Given a tree with n nodes, rooted at 1. You have q offline queries with the form of ui, vi and xi. You have to add xi to every node in the simple path from ui to vi. It is guaranteed than ui is an ancestor of vi. Then you have to print out the values of all the nodes. The limit is... well, too large for O(n^2). Could anyone give me an approach to this problem?

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

»
6 лет назад, # |
← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

Since you asked for an approach, I won't go in details, but just give the approach.

Edit: Seems like I've overkilled it for both online and offline. Refer to Bedge's solution for the simple approach.

For O(log) amortized time for a query you can use centroid decomposition. Each time you find the centroid you can process all queries that pass through it in constant amortized time per query.

Additionally, in case you want to solve the problem online, there's a O(log2) per query solution using heavy-light decomposition with lazy-propagation segment trees for the heavy paths.

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

    Thank you for your help. The term sounds very new, but i will try my best to understand it.

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

    I didn't quite understand how to process queries on centroid tree (let's say we already built it). Can you elaborate more?

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

      Boils down to pretty much Bedge's solution but even slightly simpler. However since that solution will work for the whole problem, doing centroid decomposition is an overkill.

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

        I still couldn't think of a centroid decomposition approach for this problem but there is a heavy-light decomposition approach, which is pretty much straight forward like ulna's trick but for log(n) arrays.

        → Ответить
»
6 лет назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

Another approach is to use partial sum on tree.

Spoiler
→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

https://codeforces.me/contest/1076/problem/E
Similar problem if you want to try another one.

→ Ответить