• 方法一
  • 优点
  • 缺点
• 方法二
  • 优点
  • 缺点
• 例题：
  • - CF70E Information Reform
  • - P3267 [JLOI2016/SHOI2016]侦察守卫
    • 代码
  • 模拟赛的题
  • Rbtree

• CF70E Information Reform
• P4845 LJJ爱数树
• P3267 [JLOI2016/SHOI2016]侦察守卫
• [Rbtree][]

通常，我们有两种做法：

方法一

我们对于每个点，考虑距离它最近的被选点

需要先证明一个显然的结论：对于每个i，以i为最近点的j是一个连通块。

换句话说，如果距离a的最近被选点为i，距离b的最近被选点也是i，那么a到b的路径上的点的最近被选点都是i。
考虑一条链：设Ax是链上第x个点，那么点y到Ax的距离fy(x)随x的增加，先下降，再上升。（这个显然）。
那么假设a到b路径上的c，最近点不是i而是j。
那么，\(dis(a,i)dis(c,j)，dis(b,i)。
就是说\(fi\)和\(fj\)有两个交点。但这是不可能的。
所以，如果距离a的最近被选点为i，距离b的最近被选点也是i，那么a到b的路径上的点的最近被选点都是i一定成立。

这样，这样，我们设\(dp(i,j)\)表示i的最近点是j的状态。
（如果需要，再维护\(f(i)\)表示\(dp(i,j)\)的最小值。）
那么，对于i的每个儿子v，枚举它的最近点a，则转移到\(dp(v,a)\)。
注意，如果\(j=a\)，那么对于v来说，a已经选择过了，则转移时把选j的影响去掉。

由于形成连通块，正确性可以保证。

补充：
如果信息要求更精确（因为上述做法这个最近点不一定联通，即可能重复，被考虑多次）。
在子节点v的最近点与当前点u相同时，直接转移，不需要考虑贡献。
否则，必须满足u的最近点不在v子树内，并且v的最近点在它的子树内。
这样，就可以避免重复的问题了。
每个最远点的贡献可以在\(f(u,u)\)时考虑，也可以在每个连通块的顶部考虑。

优点

适用范围较广，非常好写。

缺点

复杂度至少为\(O(n^2)\)。

方法二

维护子树信息

对于每个子树，有2种信息：

1. 当前子树中，最远的没被覆盖的点。（可能没有）
2. 当前子树中，最近的被选点还能向上覆盖多少。（可能没有）

理论上，共有4种情况，
但实际上，如果既有没被覆盖的点，又有能向上覆盖的被选点，由于没被覆盖的点需要上面的一个点覆盖，那么对于这个点来说，下面的向上覆盖的被选点已经失去意义了。

所以，只有3种情况，可以用2个dp数组，外加一维记录。

转移时依次合并，共有4种情况。
由于需要枚举两个值，因此，若覆盖范围为D，则复杂度为\(O(nD^2)\)。
因为是对两个值取max等操作，所以通过前缀最值可以优化至\(O(nD)\)。

优点

复杂度较低，便于优化。

缺点

只适用于覆盖问题，若需要在转移时知道每个点最近的被选点等信息，则只能用方法一。
同时，情况较多，代码较难写。

例题：

- CF70E Information Reform

由于要知道确切距离，只能用方法一。

- P3267 [JLOI2016/SHOI2016]侦察守卫

由于复杂度的要求，直接套用方法二即可。

代码

（未加优化）

#include 
int dp1[500010][21],dp2[500010][21],D;
int fr[500010],ne[1000010],v[1000010],bs=0;
int sz[500010],g1[21],g2[21],inf=999999999;
bool bk[500010];
void addb(int a,int b)
{
	v[bs]=b;
	ne[bs]=fr[a];
	fr[a]=bs;
	bs+=1;
}
void dfs(int u,int f)
{
	for(int i=fr[u];i!=-1;i=ne[i])
	{
		if(v[i]!=f)
			dfs(v[i],u);
	}
	for(int a=0;a<=D;a++)
		dp1[u][a]=dp2[u][a]=inf;
	dp1[u][0]=0;
	bool dy=true;
	for(int i=fr[u];i!=-1;i=ne[i])
	{
		if(v[i]==f)continue;
		if(dy)
		{
			for(int a=0;a<=D;a++)
			{
				dp1[u][a]=dp1[v[i]][a];
				dp2[u][a]=dp2[v[i]][a];
			}
			dy=false;
			continue;
		}
		for(int a=0;a<=D;a++)
			g1[a]=g2[a]=inf;
		for(int a=0;a<=D;a++)
		{
			for(int b=0;b<=D;b++)
			{
				int t=a,o=dp1[u][a]+dp1[v[i]][b];if(b>t)t=b;
				if(o=b)
				{
					if(o=a)
				{
					if(ot)t=b;
				if(o=0;i--)
		g2[i+1]=dp2[u][i];
	g1[D]=g2[0]=inf;
	if(dp1[u][0]+sz[u]

【题目背景】
Po 姐姐很爱他的妹子,可是 Po 姐姐并没有妹子。于是 Po 姐姐决定去找妹子。
【题目描述】
A 国有 n 个城镇,由 n-1 条道路连接,构成了一个树形结构。每条道路的长度都是一样
的。
Po 姐姐最近得到了一个信息:在 A 国的某些城镇,可能出现质量上乘的妹子。
为了捕获这些妹子, Po 姐姐制作了 m 个传送器,准备将这些传送器安置在一些城镇中。
一旦某个城镇出现了妹子,Po 姐姐可以立刻传送到某个传送器所在的城镇,然后沿道路移
动到妹子所在的城镇。Po 姐姐并不愿意走太多的路,因此他会选择离妹子最近的一个传送
器传送,然后走最短路到达妹子所在的城镇。
Po 姐姐想要通过合理安排传送器的位置,使得所有妹子可能出现的城镇离最近传送器
的距离的最大值最小。
由于 Po 姐姐懒癌发作,请你帮他写一个程序来解决这个问题。Po 姐姐懒得写 SPJ,你
只需要输出最大距离的最小值就行了。
【数据输入】
第一行是两个正整数 n,m,表示 A 国城镇的数量和传送器的数量
接下来 n 个整数,每个整数都是 1 或 0,如果第 i 个整数是 1 代表第 i 个城镇可能出现
质量上乘的妹子
接下来 n-1 行,每行两个正整数 x,y,表示 x 与 y 之间有一条双向通行的道路
【数据输出】
输出一行一个正整数,代表所有妹子可能出现的城镇离最近传送器的最大距离的最小值