深搜+栈

题目链接：https://ac.nowcoder.com/acm/contest/5674/K

题目大意：
有一个土拨鼠在节点1，一个橘子在节点n，在t时刻之前土拨鼠向着n走，橘子不动，从t时刻开始，橘子开始抓土拨鼠，土拨鼠开始跑，土拨鼠 1m/s， 橘子 2m/s，问还有多长时间橘子才能抓到土拨鼠。

解题思路：
幸好是一个直线运动，没有二维的考虑。
首先要求的 t 时刻土拨鼠的位置，然后土拨鼠需要逃跑，所以得与 n 点背向而跑，这时候有俩种可能
1.土拨鼠可以跑的路很长，orange抓到它也没跑到尽头。
2.土拨鼠可以跑的路很短，土拨鼠跑到路的尽头等待orange来抓它
所以得求土拨鼠能跑的最远距离， 而且因为背向而跑的，所以用相对运动的来做，他们的相对速度为1m/s，所以orange追上土拨鼠需要花费的时间，就是相对距离。
有点绕逻辑，其实主要是英文...

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
using namespace std;
const int N = 1e5 + 5;

struct node{int to;};

vector <node> G[N];
int d_hog[N], orange[N], f[N];

void dfs(int u, int fa, int d[]) {
    f[u] = fa;
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i].to;
        if (v == fa)    continue;
        d[v] = d[u] + 1;
        dfs(v, u, d);
    }
}

void dfs2(int u, int fa, int &maxx) {
    maxx = max(maxx, orange[u]);
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i].to;
        if (v == fa) continue;
        dfs2(v, u, maxx);
    }
}

int main() {
    int n, t;
    memset(d_hog, 0, sizeof(d_hog));
    memset(orange, 0, sizeof(orange));

    scanf("%d %d", &n, &t);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        G[u].push_back({v});
        G[v].push_back({u});
    }

    dfs(n, n, orange); //遍历organge是希望fa保存orange的父节点
    int hog_start = 1;
    while (t--) { //从1向上寻找t次，找到t秒候hog应该在的位置
        hog_start = f[hog_start];
    }
    int maxx = 0;
    dfs2(hog_start, f[hog_start], maxx); //求得hog背离n点而行能走的最大距离（这个距离是以n点位参考点)

    int max_dis = maxx - orange[hog_start];
    int bw_dis = orange[hog_start]; //t时刻俩者间的距离
    if (hog_start == n) printf("0\n");
    else if (max_dis >= bw_dis)   printf("%d\n", max(1, bw_dis)); //表明土拨鼠是在逃跑的路上被捉到的
    else printf("%d\n", max(1, (max_dis + bw_dis + 1)/ 2)); //表明土拨鼠是在最远处等着orange来捉
    return 0;
}