题解正向思维看起来比较难，树上DFS，当作一个图搜索，跑SPFA，枚举每种走法？但是我这种蒟蒻怎么可能会呢，于是我们要逆向思维！很容易就能想到路径就是从n往上爬，把爬的路程反向输出即可。 \sout{LCA}！因为是反向输出，所以要记录路程，可以用数组记录。但是现在可是科技化的时代，当然要用 \sout{C}++的外挂 STL了！本蒟蒻想到的可以选择的： vector向量：使用 push_front() 函数，但是众所周知vector用的是一段连续的内存，所以使用一次 push_front() 函数的时间复杂度实际上却是O(k)，其中k为此时向量中的元素。所以复杂度为O(n^{2})，会超时。使用 push_back() 函数（正常插入），输出时使用 back() 函数，再用 erase(v.end()-1) 删除，可行。 deque双端队列正常从队尾插入，再从队尾向前遍历，类似vector中的第二种方法。 stack栈各位大佬应该能够立刻想到的数据结构。因为是FILO（先进后出）的数据结构，所以它的正常操作即可以满足题目的要求（本蒟蒻用的方法）。注意一开始的时候要把n（最后走到的终点节点）给 push() 进去代码 #include<stdio.h> #include<stack> //栈的头文件 using namespace std; int n,p[200010]; stack<int> path; //栈 int main() { scanf("%d",&n); for(register int i=2;i<=n;++i) scanf("%d",&p[i]); //输入父亲节点 path.push(n); //记得先push(n) while(n!=1) //从终点开始反向遍历直到起点 { n=p[n]; //到父节点 path.push(n); //保存路径 } while(!path.empty()) //输出路径 { printf("%d ",path.top()); path.pop(); } return 0; }

洛谷CF1057A题解

damage

题解

正向思维看起来比较难，树上DFS，当作一个图搜索，跑SPFA，枚举每种走法？

但是我这种蒟蒻怎么可能会呢，于是我们要逆向思维！

很容易就能想到路径就是从n往上爬，把爬的路程反向输出即可。

~~\sout{LCA}！~~

因为是反向输出，所以要记录路程，可以用数组记录。但是现在可是科技化的时代，当然要用~~\sout{C}++的外挂~~STL了！

本蒟蒻想到的可以选择的：

vector向量：
1. 使用push_front()函数，但是众所周知vector用的是一段连续的内存，所以使用一次push_front()函数的时间复杂度实际上却是O(k)，其中k为此时向量中的元素。所以复杂度为O(n^{2})，会超时。
2. 使用push_back()函数（正常插入），输出时使用back()函数，再用erase(v.end()-1)删除，可行。
deque双端队列
- 正常从队尾插入，再从队尾向前遍历，类似vector中的第二种方法。
stack栈
- 各位大佬应该能够立刻想到的数据结构。因为是FILO（先进后出）的数据结构，所以它的正常操作即可以满足题目的要求（本蒟蒻用的方法）。

注意一开始的时候要把n（最后走到的终点节点）给`push()`进去

代码

#include<stdio.h>
#include<stack> //栈的头文件
using namespace std;
int n,p[200010];
stack<int> path; //栈
int main()
{
    scanf("%d",&n);
    for(register int i=2;i<=n;++i) scanf("%d",&p[i]); //输入父亲节点
    path.push(n); //记得先push(n)
    while(n!=1) //从终点开始反向遍历直到起点
    {
        n=p[n]; //到父节点
        path.push(n); //保存路径
    }
    while(!path.empty()) //输出路径
    {
        printf("%d ",path.top());
        path.pop();
    }
    return 0;
}