I_love_Vovuh_s_cat's blog

Need help with tree problem
By I_love_Vovuh_s_cat, history, 6 years ago, In English

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?

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

»
6 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
»
6 years ago, # |
  Vote: I like it +25 Vote: I do not like it

Another approach is to use partial sum on tree.

Spoiler
→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you for your help. This sounds simpler but i will try to be able to implement both.

    → Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply