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.
$$$ \ $$$
Waiting for jiangly or any Chinese prodigy, or simply the greatest ahmet23...
once upon a time, i claimed that the people running this exam formed a cult
now 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.
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