2020-2021:teams:hotpot:2020nowcoder4
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:hotpot:2020nowcoder4 [2020/07/24 12:58] misakatao 更新 |
2020-2021:teams:hotpot:2020nowcoder4 [2020/07/24 15:09] (当前版本) lotk |
||
|---|---|---|---|
| 行 9: | 行 9: | ||
| =====题解===== | =====题解===== | ||
| - | ====A - ==== | + | ====A - Ancient Distance==== |
| - | ===solved by === | + | ===solved by lxh=== |
| ===题意=== | ===题意=== | ||
| + | |||
| + | 我们定义远古距离为其到其最近的有标记的祖先的距离（自己有标记则为0）。现在依次给 $1~n$ 个点，问在树上有这么多标记了的点时，最大的远古距离最小是多少。 | ||
| ===数据范围=== | ===数据范围=== | ||
| + | |||
| + | 点数 $n \le 2e5 $ | ||
| ===题解=== | ===题解=== | ||
| + | |||
| + | 正面想这个问题不太好解决，我们不妨反过来想，由于答案的单调性让问题变为当最大远古距离为 $k$ 时，最少需要多少个点，这样我们就可以通过在最深的点处向上爬 $k$ 层再将整个子树去掉的方法贪心（需要借助线段树和dfn序维护），最后从 $1~n$ 扫一遍处理出每个的答案。 | ||
| ====B - ==== | ====B - ==== | ||
2020-2021/teams/hotpot/2020nowcoder4.1595566692.txt.gz · 最后更改: 2020/07/24 12:58 由 misakatao
