glays's blog

By glays, history, 3 months ago, In English,

I'm having trouble solving QTREE4 using centroid decomposition.

I don't know if it can be solved with HLD or Sqrt Decomposition nor do I know anything about these algorithms.I need help(hints would be great) on how to approach this problem using only CD.

What's bugging me the most is that edges are weighted(weights can be negative).

I'm thinking every centroid should store as many distances/answers(an answer is a distance between this centroid and a white node) below it as the number of it's subtrees(it's outdegree) and itself if it's white.That's because if we store two distances of two nodes in a centroid when this centroid isn't their LCA, we can't use these distances since the path wouldn't be simple.

Any help would be appreciated.

Thanks !

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

»
3 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

I don't exactly know what "centroid decomposition" means,and my English is poor.

I think,when you do divide and conquer,you can keep the structure,actually,the centroids form a tree.And we can prove that the height of the tree is O(logn).At first,when we do divide and conquer,we can iterate every son of the root(the centroid now) and use a heap(priority_queue) to store the maximum distance to the root of the white nodes in its subtree.We use another heap to store the maximum distance of two white nodes in this subtree(the subtree of the root we consider now) which passes the root.And another heap to store the maximum distance of two white nodes of the whole tree.When we change a node's color,we can iterate all trees which include it.There is just O(logn) trees which include the node.we can insert or delete some information in the heap and get the new answer.It's O(logn) in every tree,and totally it's O(log^2n).When we want to know the answer,just get the top of the heap of the whole tree.It's O(nlogn).

This is a code I used to solve a problem similar to QTREE4 a year ago.

http://paste.ubuntu.com/25361366/

The problem is:http://www.lydsy.com/JudgeOnline/problem.php?id=1095 ,you don't need to see it because maybe you can't read Chinese.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh!This code is unreadable!Can you try to understand what I said?

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I can't really understand the code, but after translating your problem, it's roughly the same as QTREE4 but without weights.

      Thanks for the explanation !

»
3 months ago, # |
  Vote: I like it +36 Vote: I do not like it

Why so many green and grey guys know algorithms like HLD, centroid decomposition, flows and suffix trees, but in the same time they can't solve easy tasks in div2 contests?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I haven't needed either of them in CF contests :)

    In fact, to be in div1 you don't need any "mega algorithm", ability to think faster is enough

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I have always heard about this, and that a lot of people became blue and even purple knowing only BFS,DFS and simple dp/greedy techniques, but I have no idea what I'm missing..

    I've been studying advanced graph algorithms for a while now so I kinda find it hard to believe !