#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class type1>
#define ll long long int
#define endl "\n"
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
using ordered_multiset = tree <type1, null_type, less_equal <type1>, rb_tree_tag, tree_order_statistics_node_update>;
//ordered_multiset <ll> kek;(declaration for multiorder set)
// ordered_set o_set;(declaration)
//kek.order_of_key(i);(strictly less then i for multi order set)
//o_set.order_of_key(5) ;(strictly less then i for multi order set)
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define N 100000
vector<ll>adj[N];
ll parent[N];
void dfs(ll node,ll par=-1)
{
parent[node]=par;
for(auto u:adj[node])
{
if(u==par)continue;
dfs(u,node);
}
}
vector<ll>path(ll node)
{
vector<ll>v;
while(node!=-1)
{
v.push_back(node);
node=parent[node];
}
reverse(v.begin(),v.end());
return v;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll n,i;
cin>>n;
for(i=1;i<n;i++)
{
ll u,v;
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<ll>v1;
vector<ll>v2;
dfs(1);
ll x,y;
cin>>x>>y;
v1=path(x);
v2=path(y);
ll ans;
for(i=0;i<min(v1.size(),v2.size());i++)
{
if(v1[i]==v2[i])
{
ans=v1[i];
}
else break;
}
cout<<ans<<endl;
return 0;
}
0 Comments