P1041 [NOIP 2003 Senior] Infectious Disease Control (suspected wrong problem)

本题是错题，后来被证明没有靠谱的多项式复杂度的做法。测试数据非常的水，各种玄学做法都可以通过，不代表算法正确。因此本题题目和数据仅供参考。本题的难度仅代表设计算法可以通过本题原始数据的难度。 [关于此类题目的详细内容](https://www.luogu.com.cn/paste/pf94n89x) --- 近来，一种新的传染病肆虐全球。蓬莱国也发现了零星感染者，为防止该病在蓬莱国大范围流行，该国政$ $府决定不惜一切代价控制传染病的蔓延。不幸的是，由于人们尚未完全认识这种传染病，难以准确判别病毒携带者，更没有研制出疫苗以保护易感人群。于是，蓬莱国的疾病控制中心决定采取切断传播途径的方法控制疾病传播。经过 WHO（世界卫生组织）以及全球各国科研部门的努力，这种新兴传染病的传播途径和控制方法已经研究清楚，剩下的任务就是由你协助蓬莱国疾控中心制定一个有效的控制办法。

Studies show that this infectious disease has two very special properties. First, its transmission routes form a tree. A person $X$ can only be infected by a specific person $Y$. As long as $Y$ does not get sick, or the transmission route between $X$ and $Y$ (i.e., $XY$) is cut, $X$ will not get sick. Second, the disease spreads periodically. Within one transmission period, it infects only one generation of patients, and does not spread further to the next generation in that period. These properties greatly reduce the pressure on Penglai’s disease control efforts, and they have already obtained a potential transmission map (a tree) for part of the susceptible population. However, the problem is not over. Due to limited manpower and technology, during one transmission period they can cut only one transmission route. Any remaining, uncontrolled routes will cause more susceptible people to be infected (that is, people who are connected to the currently infected by a transmission route that has not been cut). When it becomes impossible for any healthy person to be infected, the disease stops spreading. Therefore, Penglai’s CDC must decide an order in which to cut transmission routes so that as few people as possible become infected. Your program must, for the given tree, find an appropriate cutting order.

The first line contains two integers $n$ and $p$. The next $p$ lines each contain two integers $i$ and $j$, indicating there is an edge between nodes $i$ and $j$ (that is, there is a transmission route between person $i$ and person $j$). Node $1$ is already infected. The graph is a tree, so $p = n - 1$.

One line: the total number of people who get infected.

Constraints: For $100\%$ of the testdata, $1 \leq n \leq 300$. Source: NOIP 2003 Senior, Problem 4. Translated by ChatGPT 5