2020牛客暑期多校训练营（第九场）K-The Flee Plan of Groundhog

思路：因为是树，所以到某一点的路径唯一，先一遍bfs算出1到n的路径，标记深度，标记路径，然后再通过深度是t，dfs反推回t秒时所在的点。如果n的深度小于等于t说明t秒前就到n了，那不用跑了直接被抓了，取0。然后通过深度算出t秒时到n的距离，此时有两种跑法，一种是往n方向跑，一种是不往n方向跑，如果往n方向跑，那么每秒距离减3，如果不往就每秒减一，另外如果没地方跑了（也就是跑到叶子节点）就留在原地不动，每秒距离减2，bfs算最长时间即可。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstdlib>
#include<string>
#include<unordered_map>
#include<vector>
#include<list>
#include<map>
#include<set>
#define fi first
#define se second
#define pb push_back
#define me(a,b) memset(a,b,sizeof(a))
#define INIT() std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const int MAX_N=100000+5;
const int MAX_M=100000+5;
const int INF=0x7fffffff;
const int inf=1000000000;
const double EPS=1e-6;
const ull base=123;
const ll mod=998244353;
const double pi=4*atan(1.0);
int n,t;
int used[MAX_N];
vector<int>v[MAX_N];
int dep[MAX_N];
int pre[MAX_N];
int vis[MAX_N];
struct node
{
   
    int tt;
    int time;
    int val;
};
int main()
{
   
    cin>>n>>t;
    int i;
    for(i=1; i<n; i++)
    {
   
        int l,r;
        scanf("%d%d",&l,&r);
        v[l].pb(r);
        v[r].pb(l);
    }
    queue<int>q;
    dep[1]=0;
    used[1]=1;
    pre[1]=0;
    q.push(1);
    while(!q.empty())//标记深度和路径
    {
   
        int u=q.front();
        q.pop();
        for(auto i:v[u])
        {
   
            if(used[i])
                continue;
            pre[i]=u;
            used[i]=1;
            dep[i]=dep[u]+1;
            q.push(i);
        }
    }
    int x=n;
    //cout<<dep[x]<<endl;
    if(dep[x]<=t)//如果n点深度<=t，则为0
    {
   
        //cout<<1;
        cout<<0<<endl;
        return 0;
    }
    while(dep[x]!=t)//找到t秒时所在点，并且标记到n的节点。
    {
   
        vis[x]=1;
        x=pre[x];
    }
    //cout<<x<<endl;
    int tt=dep[n]-t;
    queue<node>que;
    que.push(node{
   tt,0,x});
    me(used,0);
    used[x]=1;
    int ans=0;
    while(!que.empty())
    {
   
        node u=que.front();
        que.pop();
        if(v[u.val].size()==1)
        {
   
            ans=max(ans,u.time+(u.tt+1)/2);//没地方跑了，原地等死，每秒距离减2
            continue;
        }
        for(auto i:v[u.val])
        {
   
            if(used[i])
                continue;
            if(vis[i])//向n方向跑，每秒距离减3
            {
   
                used[i]=1;
                node tmp;
                tmp.val=i;
                tmp.tt=u.tt-3;
                tmp.time=u.time+1;
                if(tmp.tt>0)
                {
   
                    que.push(tmp);
                }
                else
                    ans=max(ans,tmp.time);
            }//不往n方向跑，每秒距离减1
            else
            {
   
                used[i]=1;
                node tmp;
                tmp.val=i;
                tmp.tt=u.tt-1;
                tmp.time=u.time+1;
                if(tmp.tt>0)
                {
   
                    que.push(tmp);
                }
                else
                    ans=max(ans,tmp.time);

            }
        }
    }
    cout<<ans<<endl;
}