My favorite problem during the camp Full score is 7 points, but I got 10 points on this problem

Please picture me In the trees I hit my peak at seven feet

(if you can't understand then you might need to learn tree DP and centroid decomposition first) well I forget the negatives, but whatever

laura0105_somali wrote: The REAL country has $n$ islands, and there are $n-1$ two-way bridges connecting these islands. Any two islands can be reached through a series of bridges. Arctan, the king of the REAL country, found that it is too difficult to manage $n$ islands, so he wants to bomb some islands and their connecting bridges to divide the country into multiple small areas. Arctan wants the number of connected islands in each group is less than $\delta n$ after bombing these islands, and the island he bomb must be a connected area. Besides, Arctan wants the number of islands to be bombed to be as less as possible. Find all real numbers $\delta$ so that for any positive integer $n$ and the layout of the bridge, the method of bombing the islands is the only one. Proposed by chengbilly

$\boxed{\text{Solution}}$: There are $n$ vertices and $n-1$ edges in the graph, so the graph must be a tree I will use $f_{\delta}(G)$ to denote the least number of connected vertices we have to bomb in graph $G$ so that the size of any connected component is less then $\delta |E(G)|$ ————————————————————————————————————————————————————————————————— Case1. $\delta \in (1,\infty)$ then $f_{\delta}(G)=0$ so the method of bombing the island is only one (Don’t bomb anything) $\therefore \delta \in (1,\infty)$ is a solution ————————————————————————————————————————————————————————————————— Case2. $\delta \in (\frac{1}{2},1]$ let’s consider a chain with $n=2m+1$ vertices. If $\delta > \frac{m+1}{2m+1}$ then $f_{\delta}(G)=1$ but whether we bumb the $m-1^{th}$, $m^{th}$ or $m+1^{th}$ vertice, we can ensure the size of any connected component is less then $\delta |E(G)|=m+1$, so the method of bombing the island is not only one $\therefore\forall m\in \mathbb{N}$, $1\geq \delta > \frac{m+1}{2m+1}$ is not a solution. since $lim_{m \to \infty}\frac{m+1}{2m+1}=\frac{1}{2}$, $\therefore \delta \in (\frac{1}{2},1]$ is not a solution ————————————————————————————————————————————————————————————————— Case3. $\delta = \frac{1}{2}$ applying the property of centroids in a tree. Case3.1. if $2 \nmid |V(G)|$ then there is only one centroid in the graph we can easily bomb the centroid and separate the tree into two connected component with $\frac{n-1}{2}$ vertices $\therefore f_{\frac{1}{2}}(G)=1$ if the vertice we bomb is not the centroid, then after bombing there would be a connected component with at least $\lfloor \frac{n}{2} \rfloor$, so the method of bombing is only one Case3.2. if 2||V(G)| Case3.2.1. if there are only one centroid in the tree after bombing the centroid we can separate the tree into two connected component with $\frac{n}{2}$ and $\frac{n-2}{2}$ vertices respectively. If there are more than $1$ vertices in the $\frac{n}{2}$-vertices-component, then after bombing the tree would be separate into more then $2$ connected component and each contain less then $\frac{n}{2}$ vertices, so $f_{\frac{1}{2}}(G)=1$ If there is only $1$ vertice in the $\frac{n}{2}$-vertices-component, then we bomb the connected vertice in the meantime, and the condition is satisfied, so $f_{\frac{1}{2}}(G)=2$ In the above $2$ cases, the method of bombing are both only one. Otherwise, there exists a connected component with at least $\frac{n}{2}$ vertices Case3.2.2. if there are two centroids in the tree after bombing both centroids we can separate the tree into two connected components with at least $\frac{n-2}{2}$ vertices, so $f_{\frac{1}{2}}(G)=2$ If one of the island we bombed is not the centroid, then we have at least one connected component with at least $1+\frac{n-2}{2}=\frac{n}{2}$ vertices (remember that the island we bombed must ne connected), so the method of bombing is only one $\therefore \delta =\frac{1}{2}$ is always a solution ————————————————————————————————————————————————————————————————— Case4. $\delta \in (0,\frac{1}{2})$ (the most difficult part) it’s easy to prove we can bomb some connected island to make the size every connected components less then$\delta n$. If $n \leq 2$ we can just bomb all of the island, now suppose $n>2$ consider one of the bombing-least-island methods, let the set $S$ denotes islands we bombed, and after bombing, we separate the tree into $f_{\delta}(G)=k$ connected components $S_1$, $S_2$,……$S_k$ ($1 \leq |S_i|< \delta n$ $\forall i$) Before bombing, notice that for $1 \leq i \leq k$, $S_i$ is a tree with exact one edge connected to $S$ Case4.1. $f_{\delta}(G)=|S|>1$ Suppose there exists another method of bombing $f_{\delta}(G)$ island and satisfied the condition, we must bomb at least one vertice in $S_i$ for some $i$ and also preserved at least one island in $S$ from But since $|S_i| \leq \delta n$ we know even we don’t bomb the vertice in $|S_i|$, the condition is also satisfied. So we bpcan bomb less then $k-1<f_{\delta}(G)$, contradiction! So the method of bomb is only one Case4.2 $f_{\delta}(G)=|S|=1$ if we don’t bomb an island in $S_i$ instead the only point in $S$ then $\sum_{j=1}^{i-1}|S_j|< \delta n <\frac{n}{2} $ $\longrightarrow$ $\sum_{j=1}^{i-1} \leq\lfloor\frac{n}{2} \rfloor-1$ But $|S_i|$ is also less than $\delta n$ $\longrightarrow$ $|S_i| \leq \lfloor \frac{n}{2} \rfloor -1$ So $n-1=\sum_{j=1}^i |S_j| \leq 2\lfloor \frac{n}{2} \rfloor -2 \leq n-2$, contradiction! So the method of bombing is only one $\therefore \delta \in (0,\frac 12)$ is a solutiom ————————————————————————————————————————————————————————————————— Case5. $\delta \in (-\infty,0]$ It’s triviral that whether you bomb these island, the size of every connected component is non-negtive, so $\delta <0$ is not a solution since we don’t have any method of bombing ————————————————————————————————————————————————————————————————— In conclusion, the answer is $\boxed{\delta \in (0,\frac 12] \cup (1,\infty)}$