题目链接🔗:吃桃

题意简述

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

解题思路

一共分为两步:

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