木のパスを調べる方法はいくつかありますが、ここでは深さ優先探索とstack(deque) を用いる方法を紹介します。

グラフにおける深さ優先探索とは、ある頂点 \(S\) から始めて、次の操作を繰り返すことで頂点 \(S\) から辺に沿って移動できる全ての頂点を列挙する手法です。また、各頂点 \(v\) に対してその頂点に到達した事があるかを示す \(flag[v]\) も持っておきます。最初、全ての頂点について \(flag[v]=False\) です。

1. 現在いる頂点 \(v\) について、\(flag[v]=True\) に変更する。
2. \(v\) から移動できる頂点 \(w\) であってまだ訪ねていないもの、すなわち \(flag[w]=False\) であるようなものを選び、頂点 \(w\) に移動した後、 \(1.\)から再度行う。
3. \(2.\)においてそのような頂点が存在しない場合、現在いる頂点がスタートした頂点 \(S\) であるならば探索を終了する。 そうでない時、この頂点を初めて訪れる直前のマスに戻り、\(2.\)の作業を再開する。

さて、dequeを用いてパスの頂点列を得るには頂点 \(X\) から始めて、上の作業にいくつかの項目を付け加えた次のもの繰り返せば良いです。 最初、dequeの中身は空です。

1. duque の末尾に \(v\) を追加する。
2. 現在いる頂点 \(v\) について、\(flag[v]=True\) に変更する。
3. \(v\) から移動できる頂点 \(w\) であってまだ訪ねていないもの、すなわち \(flag[w]=False\) であるようなものを選び、頂点 \(w\) に移動した後、 \(1.\)から再度行う。
4. duque の末尾から要素を \(1\) つ削除する。（ここで、削除される要素は \(v\) 自身となる）
5. \(3.\)においてそのような頂点が存在しない場合、現在いる頂点がスタートした頂点 \(X\) であるならば探索を終了する。 そうでない時、この頂点を始めて訪れる直前のマスに戻り、\(2.\)の作業を再開する。

答えは頂点 \(Y\) をdequeの末尾に付け加えた直後のdeque の中身を 手前から順に出力したものになります。

まず、これは頂点 \(X\) から頂点 \(Y\) へのパスとなっています。 さらに深さ優先探索において同じ頂点について \(1.\) が \(2\) 回以上行われることはないため、これはさらに単純パスになっています。 今、木において単純パスはただ \(1\) つとわかっているため、これが答えとなります。

他にも、さまざまな方法があります。 例えば、木を、\(Y\) を根とした根付き木として考えて、頂点 \(X\) から親の頂点に戻ることを\(Y\)に到達するまで繰り返すと、それは単純パスになります。

c++ による実装例

#include <bits/stdc++.h>
using namespace std;

vector<int>e[200010];
bool flag[200010];
deque<int> deq;
bool stop;
 
void dfs(int k,int to){
	if(!stop)deq.push_back(k);
	if(k==to)stop=true;
    flag[k]=true;
	int sz=e[k].size();
    for(int i=0;i<sz;i++){
        if(!flag[e[k][i]])dfs(e[k][i],to);
    }
	if(!stop)deq.pop_back();
	return;
}

int main(void) {
    int n,x,y;
    int u,v;

	cin>>n>>x>>y;
    for(int i=0;i<n-1;i++){
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
    }

    for(int i=1;i<=n;i++)flag[i]=false;
    stop = false;
　dfs(x,y);

    while(!deq.empty()){
		cout<<deq.front();
		deq.pop_front();
		if(deq.empty())cout<<endl;
		else cout<<" ";
	}
	return 0;
}