### tatavayapmabulldogvd's blog

By tatavayapmabulldogvd, 4 months ago, #### The Problem

You are given a tree with $N$ ($1 \le N \le 10^5$) vertices.

You need to partition the vertices into minimum number of sets, such that every set has a maximum size of $S$ ($1 \le S \le N$) and maximum distance between any of the two vertices, that are in the same set is less than $2K$ ($1 \le K \le 20$).

With a more formal statement, assuming vertices in the tree are labeled $[1, N]$ and $dist(v, u)$ is defined as the distance between two vertices in the tree, you need to find a partition $\{ P_0,\, P_1,\, \dots ,\, P_{C-1} \}$ with minimum $C$, such that:

• for every $\displaystyle P_i, \ max_{\ \forall v,\ u \ \in P_i} \{dist(v, u)\} \le 2K$
• for every $\displaystyle P_i, \ |P_i| \le S$
• for every $\displaystyle 1 \le x \le N, \ x \in \bigcup P_i$

The problem doesn't want you to print the partition, you only need to print it's size (number of sets) and note that it's not necesseary for vertices in a set to form a connected component.

$\$

My manners
My ideas  Comments (8)
 » Waiting for jiangly or any Chinese prodigy, or simply the greatest ahmet23...
 » 4 months ago, # | ← Rev. 2 →   once upon a time, i claimed that the people running this exam formed a cultnow with this, i stand behind my judgement even more firmly
 » I have feeling that you can get up to ~%72 points if the cases are not well prepared with cout << (n+s-1)/s << endl;
 » I guess there may be a greedy solution based on something like Chordal Graph Theory.
 » https://www.acmicpc.net/problem/8169 looks similar.
•  » » 4 months ago, # ^ | ← Rev. 2 →   Yeah, it was identical (I'll look into your code more carefully when I'm free, it looks like I'm missing something that makes merging subtrees pretty easy, thanks for the lead)
 » I think there is a typo. There should be $max_{\forall v,u \in P_i} dist(v,u)$ not $min$.
•  » » You're right, sorry fixed it now