题解
正向思维看起来比较难,树上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;
}