When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

orangeorange's blog

By orangeorange, history, 4 years ago, In English

There is a problem 293E - Close Vertices. Is it possible to solve it with Centroid Decomposition? How?

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

»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

I can do it in $$$O(n\log^3 n)$$$time. Divide and Conquer on Tree: pick a node, count valid paths passing through that node, then delete the node and do the same for each component. The node to pick is the Centroid of the tree. So how to count the paths passing through some node $$$u$$$? Well, root the tree at $$$u$$$, let’s say $$$u$$$’s children are $$$v_1,v_2,\dots, v_k$$$, do a DFS on each $$$v_i$$$’s subtree computing length and weight of paths from $$$u$$$ to all nodes. Now for each node node $$$j$$$ in the subtree of $$$v_i$$$ (let’s say length and weight from $$$u$$$ to $$$j$$$ are $$$L_j$$$ and $$$W_j$$$ respectively) we need to count how many nodes $$$k$$$ (not belonging to $$$v_i$$$’s subtree) are there such that $$$L_k\le l-L_j$$$ and $$$W_k\le w-W_j$$$. For that we can use a 2D data structure: let’s suppose we have a matrix where in position $$$(i,j)$$$ there is the amount of nodes $$$x$$$ such that $$$L_x=i$$$ and $$$W_x=j$$$, we can use a 2D-Segment Tree to add +1 to some position and ask for sum of a subrectangle in the matrix in $$$O(\log^2 n)$$$, so final complexity is $$$O(n\log^3 n)$$$, this might fit in time.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    also you can replace the 2D segment Tree for a 2D-BIT (but implemented with dynamic memory).

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

    It will never fit in memory

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

      Hey...it’s just $$$O(n\log n)$$$ memory.

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

      I use a binary indexed tree, and on each node I keep a Reb Black Tree.

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

        Ok, I thought from your approach that 2D Segment Tree will not fit memory

»
4 years ago, # |
Rev. 4   Vote: I like it +11 Vote: I do not like it

1) Run the centroid decomposition algorithm

2) Let the centroid now be some node $$$v$$$

3) Write down all the nodes that lie in the same component with $$$v$$$ (the tree will split into components, because there were already some centroids earlier and we do not pass through them)

4) Sort these nodes by $$$dist[i][v]$$$ (distance from $$$i$$$ to $$$v$$$).

5) Build a fenwik tree in each node of which we will store decart tree. The key in the decart tree will be $$$w[i]$$$ ($$$w[i]$$$ is the sum of the weights of the edges on the path from $$$v$$$ to node $$$i$$$)

6) Iterate over the neighbors of node $$$v$$$ and delete all the subtree of this neighbor from the decart tree, so that we don't consider vertices from the same subtree, otherwise we can't guarantee that the shortest path between them passes through the centroid. Iterate through all the vertices of the subtree. Let us now choose a node $$$u$$$. So that the distance between the nodes is less than or equal to l, we must take some prefix of the array, such that for all i of this prefix, $$$dist[i][v] + dist[u][v] \leq l$$$ is executed (this can be done using binary search for $$$O(\log(n))$$$). Now in the fenwik tree, take the data prefix and find the number of nodes for $$$O(\log(n))$$$ such that $$$w[i] \leq w - w[u]$$$.

7) Divide the answer by $$$2$$$, because each pair is counted twice. Thus, the final asymptotics will be $$$O(n\log^3(n))$$$