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

# | User | Rating |
---|---|---|

1 | tourist | 3748 |

2 | Benq | 3540 |

3 | Petr | 3470 |

4 | Radewoosh | 3355 |

5 | ecnerwala | 3347 |

6 | maroonrk | 3345 |

7 | jiangly | 3324 |

8 | scott_wu | 3313 |

9 | ainta | 3298 |

10 | boboniu | 3289 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 200 |

2 | Errichto | 196 |

3 | rng_58 | 194 |

4 | SecondThread | 186 |

5 | awoo | 185 |

6 | Um_nik | 182 |

7 | vovuh | 179 |

8 | Ashishgup | 176 |

9 | maroonrk | 174 |

10 | -is-this-fft- | 173 |

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

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/28/2021 13:11:51 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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.

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

It will never fit in memory

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

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

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

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 treein each node of which we will storedecart 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))$$$