The Flee Plan of Groundhog
题目大意：
有一个土拨鼠在节点1，一个橘子在节点n，在t时刻之前土拨鼠向着n走，橘子不动，从t时刻开始，橘子开始抓土拨鼠，土拨鼠开始跑，土拨鼠 1m/s 橘子 2m/s，问还有多长时间橘子才能抓到土拨鼠。
解题思路：
t 时刻之后，土拨鼠必然朝着n的反方向移动，土拨鼠走一步，橘子走两步，那么我们可以记录一下t时刻土拨鼠的位置，还有土拨鼠向反方向最多能跑多远。如果土拨鼠向后跑了一步就到头了，那么显然答案是橘子到该点的距离/2向上取整，但是如果土拨鼠可以向后跑很多步，在跑的过程中被逮住了，那么答案就是土拨鼠往后跑的距离的时间。
- 土拨鼠向后跑到了最远处没法再跑蹲躲在角落等着橘子来抓
- 土拨鼠向后跑的过程中被橘子逮住了
分类讨论一下即可。
Code：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=500000;vector<int> ve[maxn];
int dis[maxn],f[maxn],m,ed=1,maxx=0;void dfs(int x,int pre,int val){ //记录下每个点到n的距离 f[x]=pre;dis[x]=val;for(int i=0;i<ve[x].size();i++){if(ve[x][i]==pre) continue;dfs(ve[x][i],x,val+1);}
}void dfs2(int x,int pre){maxx=max(maxx,dis[x]); //从t时间所在地点往n点相反的方向跑最远是多少for(int i=0;i<ve[x].size();i++){if(ve[x][i]==pre) continue;dfs2(ve[x][i],x);}
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t,n,tmp=1;cin>>n>>m;for(int i=1;i<n;i++){int u,v;cin>>u>>v;ve[u].push_back(v);ve[v].push_back(u);}dfs(n,n,0);while(m--) tmp=f[tmp]; //找出土拨鼠的t时间所在的节点 dfs2(tmp,f[tmp]);int x=maxx-dis[tmp]; int y=dis[tmp]; // 拨鼠的t时间所在的节点到n的距离 if(tmp==n) cout<<"0\n"; //土拨鼠在t时间之前到了n点 else if(x-y>=0) cout<<max(1,y)<<endl; //土拨鼠跑到最远点之前被橘子逮住了 else cout<<max(1,(maxx+1)/2)<<endl; // 土拨鼠跑到最远点了然后没法再跑了，躲在角落等着橘子来抓 return 0;
}