Nowcoder girl 2019：第二题 吃桃

题目链接🔗：吃桃

题意简述

这题要在有 个点的连通图中，以点 为起点，找到一条深度最深（长度最长）的路径，并且把路径记录下来。

解题思路

一共分为两步：

1. DP+DFS 找到每个点的所有子节点的最长深度，记录在 中， 为父节点的编号。

2. 贪心递归 每次都选能走到最长深度的那个子节点。

注意点

-这个是无向图，如果a，b之间有边，要互存为父节点和子节点。为了防止遍历的时候走回来，记得开个 记录已经走过的点。【这题的OJ数据很弱，没有环。之前比赛时的代码没有记录每个节点是否走过，只在遍历的时候跳过父节点，也可以AK。但是在有环的情况下会死循环（吃掉的桃子又重新长出来了hhh，根据题意其实数据可以带环的，反正走过一遍之后桃子就被吃掉了，就得走别的有桃子的路径，没桃子就 路径结束）】

-图用数组模拟的链表存或者vector二维数组存都可以，都挺好写的，没啥区别（>-<定义变量的时候看起来整齐一点，我就用vector了）

代码

#include <iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 100010;

bool st[N];//用来存这个节点有没有被走过
vector<int> a[N];//开一个二维数组来保存节点之间的连接
vector<int> w[N];//储存每个点出发的多种方案吃到的桃子数
vector<int> ans;//保存经过的节点

int dfs(int t) {
    st[t]=true;
    int mx = 0;
    for (auto it : a[t]) {//对于所有和t相接的点都继续遍历，得到它的深度
        if (st[it] == true) {//跳过走过的点
            w[t].push_back(-1);
            continue;
        }
        int v = dfs(it);
        st[it]=false;
        w[t].push_back(v);//把每个子节点的最大深度存下来
        mx = max(mx, v);//选取最大的作为这个节点的深度备选
    }
    return mx + 1;//这个就是该点的深度了
}



void getans(int t) {
    ans.push_back(t);//先把选到的点t存到路径里
    st[t]=true;
    int mxid = -1, mxval = -1;//用来记录下游节点里路径最长的点的编号和长度
    for (int i = 0; i < a[t].size(); ++i) {//对于点t的每个下游节点，找到一个深度最大的点
        int it = a[t][i];
        if (st[it] == true) continue;//如果是走过的点就跳过
        if (w[t][i] > mxval) {
            mxid = it;     
            mxval = w[t][i];
        }
    }
    if (mxid == -1) return;//没有下游节点的时候，我们就找完啦~
    getans(mxid);//有下游节点时继续找下游节点的最长路径
    st[mxid]=false;
}

int main()
{
    int n, k;//节点数n，和起点k
    int ta, tb;
    cin >> n >> k;
    for (int i = 0; i < n - 1; ++i) {
        cin >> ta >> tb;
        a[ta].push_back(tb);//用a[i][?]来保存与第i个节点相邻的所有节点编号
        a[tb].push_back(ta);//因为是无向图，双方互通
    }
    dfs(k);//每个点的所有子节点的最长深度
    getans(k);//得到最长路径的点编号，存在ans内

    //依次输出ans容器中保存的路径
    for (auto it : ans) cout << it << endl;
    return 0;
}