ABC 270 C - Simple path（树+dfs）

第一次写出比较正经的树+dfs，这不得写篇博客

题目大意：
给定一棵树，具有n个节点，给定n-1条边，给定一个起点和终点，

让我们输出从起点到终点的路径。

Sample Input 1 
Copy
5 2 5
1 2
1 3
3 4
3 5
Sample Output 1 
Copy
2 1 3 5

Sample Input 2 
Copy
6 1 2
3 1
2 5
1 2
4 1
2 6
Sample Output 2 
Copy
1 2

把每个初始节点看成父节点

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1000020;
const LL N=200200,M=2002;
LL n,be,ed;
vector<LL> v,g[N];
void dfs(LL idx,LL fa)
{
    if(idx==ed)
    {
        for(LL i=0;i<v.size();i++)
            cout<<v[i]<<" ";
        return ;
    }
    if(g[idx].size()==0)//走到叶子节点直接退回
    {
        return ;
    }
    for(LL i=0;i<g[idx].size();i++)
    {
        LL j=g[idx][i];
        if(j==fa) continue;//特判父节点
        v.push_back(j);
        dfs(j,idx);
        v.pop_back();//状态回溯
    }
}
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    cin>>n>>be>>ed;
    for(LL i=1;i<=n-1;i++)
    {
        LL a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    v.push_back(be);
    dfs(be,-1);//根节点的父节点是-1，表示他没有父节点
    return 0;
}