题目大意

  • 给定一棵有n个节点，n-1条边的树，每条边长度为1，开始土拨鼠在1号节点，沿着最短路走向n号。
  • 土拨鼠出发t秒钟后，Orange以2m/s的速度跑向土拨鼠，而土拨鼠以1m/s的速度向任意方向逃跑。设每秒钟土拨鼠先移动Orange再移动。土拨鼠可以选择留在原地。
  • 求Orange最晚几秒钟能追上他。

解题思路

思路一

二分时间t，判断在t内土拨鼠是否会被追上。
每次都以Orange所在的寝室为根建树，从1到n枚举所有的土拨鼠能够到达的点，然后判断在走的过程中会不会被追上。

这个思路比赛时想到过，就是走一步看一步，只是后来举出几个“反例”，以为很难实现。

思路二

  • 我们先以Orange为起点，DFS出Orange到每个点的时间，记为O数组；
    再以走了t秒后土拨鼠的位置为起点DFS，求出它到每个点的时间，记为G数组。
    这里的所有时间都不包含弯路，因为土拨鼠走弯路就相当于缩短距离白给。
  • 最后再次DFS，寻找最远的第一个O值与G值重合的点，即土拨鼠最远能跑到的位置。
  • 但是，也有无处可逃，原地等的情况，而有时这样会成为最佳方案。在判断时就取Orange来收人的O数组即可。

时间复杂度

思路一为O(n log n)，思路二为O(n)（实际上是三次DFS）。

AC代码（思路二）

思路一的代码等标程出了再打吧（咕咕咕）

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
vector<int> v[N];
int G[N],O[N],f[N],n,ans=-1;
void dfs(int x,int step,int fa)
{
    O[x]=step/2;
    int t,i;
    for(i=0;i<v[x].size();i++)
    {
        t=v[x][i];
        if(t==fa) continue;
        dfs(t,step+1,x);
    }
}
void ddfs(int x,int step,int fa)
{
    G[x]=step;
    for(int i=0;i<v[x].size();i++)
    {
        int t=v[x][i];
        if(t==fa) continue;
        f[t]=x;
        ddfs(t,step+1,x);
    }
}
void dddfs(int x,int fa)
{
    bool flag=0;
    int t,i;
    for(i=0;i<v[x].size();i++)
    {
        t=v[x][i];
        if(t==fa) continue;
        flag=1;
        if(G[t]>=O[t])
        {
            ans=max(ans,O[x]);
            continue;
        }
        dddfs(t,x);
    }
    if(!flag) ans=max(ans,O[x]);
}
int main()
{
    int t,x,y,i,j;
    scanf("%d%d",&n,&t);
    for(i=1;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    ddfs(1,0,-1);
    x=G[n]-t;
    if(x<=0) puts("0");
    else
    {
        i=n,j=x+1;
        while(j) y=i,i=f[i],j--;
        dfs(n,1,-1);
        ddfs(y,0,-1);
        dddfs(y,-1);
        printf("%d\n",ans);
    }
}