牛客多校第九场 The Flee Plan of Groundhog（dfs）

本文主要是介绍牛客多校第九场 The Flee Plan of Groundhog（dfs），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：
A在点1，B在点n。A先一直往B走t秒，每秒走1m，一条边1m。
t秒后A可以任意走，且B速度为2m/s。A先走一秒B再走一秒，问最迟多久A可以被B抓住。

思路：
只需要考虑A到一个点的时间和B到一个点的时间，只要在这个点A早于B，那就可以算出A被抓住的时间了。
$d 2 [i] * 2 < = d 3 [i]$ 也就是要满足，d2为A离i的距离，d3为B离的距离。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>using namespace std;
typedef long long ll;
const int maxn = 2e5 + 7;
const int mod = 1e9 + 7;int f[maxn],d1[maxn],d2[maxn],d3[maxn];
vector<int>G[maxn];void dfs1(int x,int fa) {for(int i = 0;i < G[x].size();i++) {int v = G[x][i];if(v == fa) continue;f[v] = x;d1[v] = d1[x] + 1;dfs1(v,x);}
}void dfs2(int x,int fa) {for(int i = 0;i < G[x].size();i++) {int v = G[x][i];if(v == fa) continue;d2[v] = d2[x] + 1;dfs2(v,x);}
}void dfs3(int x,int fa) {for(int i = 0;i < G[x].size();i++) {int v = G[x][i];if(v == fa) continue;d3[v] = d3[x] + 1;dfs3(v,x);}
}int main() {int n,t;scanf("%d%d",&n,&t);for(int i = 1;i < n;i++) {int x,y;scanf("%d%d",&x,&y);G[x].push_back(y);G[y].push_back(x);}dfs1(1,-1);if(t >= d1[n]) {printf("0\n");return 0;}int num = d1[n],pos = 1;for(int i = n;i;i = f[i]) {if(d1[i] == t) {pos = i;break;}}dfs2(pos,-1); //求出逃跑点到其他点距离dfs3(n,-1); //求出终点到其他点的距离int ans = 0;for(int i = 1;i <= n;i++) {if(d2[i] * 2 <= d3[i]) {ans = max(ans,(d3[i] + 1) / 2);}}printf("%d\n",ans);return 0;
}