链接
https://ac.nowcoder.com/acm/contest/5674/K
题意
树根为 $1$，A 在 $1$，B 在 $n$，A 每秒走 $1$ 步，B 每秒走 $2$ 步，开始时 A 向 B 走，经过 $t$ 秒后，B 去追 A，A 随意移动或者不移动使自己不被 B 抓到，问 B 最晚经过几秒抓到 A
思路
以 $n$ 为根 DFS，计算每个点到 $n$ 的距离
找到 $t$ 秒后 A 的位置，从这个点开始 BFS，如果被抓到了，则更新答案，否则继续 BFS，当走到叶子节点还没被抓到，那么 B 走到该叶子节点的时间就是抓到 A 的时间，也更新一下答案
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| #include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
const int N=1e5+5;
int n,t,dist[N],fa[N],mx[N];
vi G[N];
bool st[N];
void dfs(int u) {
for(auto v:G[u]) {
if(v==fa[u]) continue;
fa[v]=u;
dist[v]=dist[u]+1;
dfs(v);
}
}
int find(int u) {
for(int i=1;i<=t;i++) u=fa[u];
return u;
}
void bfs() {
int res=0;
int s=find(1);
queue<pii> q;
q.push(mp(s,0));
st[s]=true;
while(q.size()) {
auto x=q.front();
q.pop();
if(2*x.se>=dist[x.fi]) {res=max(res,x.se);continue;}
else {
bool f=false;
for(auto v:G[x.fi]) if(!st[v]) f=true,st[v]=true,q.push(mp(v,x.se+1));
if(!f) res=max(res,(dist[x.fi]+1)>>1);
}
}
printf("%d\n",res);
}
int main() {
scanf("%d%d",&n,&t);
for(int i=1;i<n;i++) {
int u,v;
scanf("%d%d",&u,&v);
G[u].pb(v);
G[v].pb(u);
}
for(int i=1;i<=n;i++) fa[i]=i;
dfs(n);
bfs();
return 0;
}
|