2020暑期牛客多校训练营第九场（K）The Flee Plan of Groundhog（lca，树形dp）

The Flee Plan of Groundhog

原题请看这里

题目描述：

疫情爆发后，土拨鼠格外小心，因此他提早在$1 ^ {st}$卧室戴上口罩，然后走到${n ^ {th}}$宿舍的路上与奥兰治一起玩。 $ZLZX$中有${n}$个宿舍，它们通过${n-1}$条走廊相连。每个宿舍可以互相到达。每个走廊的长度为${1}$。土拨鼠的步行速度为${1 \ \mathrm {m / s}}$。
那时有个坏消息来了：土拨鼠出发${t}$秒后，奥兰治拿了他的体温，结果是$41℃！！！$除了悲伤和愤慨之外，奥兰治还决定跑到土拨鼠那里，以${2 \ \ mathrm {m / s}}$的速度告诉他这个消息。
当然，土拨鼠必须跑步，但是他的速度太慢了${1 \ \mathrm {m / s}}$。在他跑步时，他有一个主意：如果他以最佳策略跑步，$Orange$多久能赶上他？定义每秒钟土拨鼠移动一次，然后橙色再次移动。土拨鼠可以选择留在原地。
土拨鼠当然可以解决这个问题，但是他现在正在逃跑，所以他把它交给了你，最聪明的一个。

输入描述：

第一行包含两个整数${n，t}$。
接下来的${n-1}$行，每行包含两个整数${x，y}$，表示在${x ^ {th}}$宿舍和${y ^ {th}}$宿舍之间有一条走廊。

输出描述：

一个整数，指示$Orange$捕获土拨鼠的最长时间。

样例输入：

7 2
1 2
2 5
5 7
5 6
3 6
3 4

样例输出：

1

说明：

After t seconds, Groundhog is in the 5th dormitory and Orange is in the 7th dormitory.
At this point, the best way for Groundhog is to goto the 2nd dormitory or the 6 th dormitory.
But wherever he goes, he will be immediately caught by Orange.

思路：

首先我们来看下面的图（样例）：

我们发现$mouse$在这时无论走到$2$还是$6$都会在下一秒被$Orange$抓到。（好水），所以答案为1.
这个图比较水…
我们换一张较为复杂的图来分析：

在这张图中，蓝色数字表示$mouse$到达该节点所需秒数，红色数字表示$Orange$到达该节点所需秒数（假定t秒已过）
这些数字一标，我们发现：$mouse$肯定不会到达红色数字小于蓝色数字的节点，因为这样$mouse$直接就被抓走了…所以我们只要判断一下红色数字和蓝色数字的大小就好了。

AC Code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e5+5;
vector<int> vec[MAXN];
int n,t,x,y,dep2[MAXN],root,dep1[MAXN],ans,fa[MAXN];
void dfs(int pos,int deep,int fx){
	dep1[pos]=deep;
	for(int i=0;i<vec[pos].size();++i){
		int v=vec[pos][i];
		if(v==fx) continue;
		fa[v]=pos;
		dfs(v,deep+1,pos);
	}
}//前一个dfs1函数用来计算t秒后mouse的位置
//后一个dfs1用来计算以土拨鼠所在节点为根节点，到其他所有节点的秒数，用dep1[]储存
void dfs2(int pos,int deep,int fx){
	dep2[pos]=deep/2;//Orange每秒可以过两条边
	for(int i=0;i<vec[pos].size();++i){
		int v=vec[pos][i];
		if(v==fx) continue;
		dfs2(v,deep+1,pos);
	}
}//以Orange所在节点为根节点，求出到其他所有节点的秒数，用dep2[]储存
void dfs1(int pos,int fx){
	int flag=0;
	for(int i=0;i<vec[pos].size();++i){
		int v=vec[pos][i];
		if(v==fx) continue;
		flag=1;
		if(dep1[v]>=dep2[v]){
			ans=max(ans,dep2[pos]);
			continue;
		}
		dfs1(v,pos);
	}
	if(!flag) ans=max(ans,dep2[pos]);
}//计算答案
int main(){
	scanf("%d%d",&n,&t);
	for(int i=1;i<n;++i){
		scanf("%d%d",&x,&y);
		vec[x].push_back(y);
		vec[y].push_back(x);
	}
	dfs(1,0,-1);
	int go=dep1[n]-t;
	ans=-1;
	if(go<=0){puts("0");return 0;}
	for(int i=n,j=go+1;j;i=fa[i],j--) root=i;//计算t秒后土拨鼠的位置
	dfs2(n,1,-1);//Orange到树上所有点的时间
	dfs(root,0,-1);//mouse到树上所有点的时间
	dfs1(root,-1);//搜索答案
	printf("%d\n",ans);
	/*
	14 1
	1 2
	2 3
	3 4
	4 5
	5 6
	6 7
	3 8
	8 9
	9 10
	10 11
	11 12
	12 13
	13 14
	*/
	/*
	ans=6
	*/
}

本文地址：https://blog.csdn.net/s260127ljy/article/details/107884652