[arc116_e]Spread of Information - 题目详情 - gxyz

ID: 2591

传统题

3000ms

1024MiB

难度: 7

上传者:

标签>

2200+

给定一棵 $N$ 个点的树。
要求在树上选择 $K$ 个关键点 $p_1,p_2,\dots,p_K$ ，使得 $\max\limits_{i=1}^N\min\limits_{j=1}^K dis(i,p_j)$ 最小。其中 $dis(i,p_j)$ 是指树上 $i$ 到 $p_j$ 的最短路径经过的边数。
数据范围： $1\le K<N\le 2\times 10^5$ 。
Translated by pitham（脾土蛤蟆）。