2020暑假牛客多校第九场 K The Flee Plan of Groundhog （树形结构/思维）

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;
}