tarjan lca
wenge
2020-08-05 22:10:23
```cpp
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define clr(a,b) memset(a,b,sizeof(a))
#define PRINT(x) cout<<#x<<" = "<<x
#define br cout<<"\n"
#define N 200005
ll n,q,m,s,ans;
vector<ll> f[500005];
ll head[1000005],nxt[1000005],to[1000005],res[500005],e,vis[500005];
void add_req(ll x,ll y){
e++;nxt[e]=head[x];head[x]=e;to[e]=y;
e++;nxt[e]=head[y];head[y]=e;to[e]=x;
}
ll p[500005];
ll find(ll x){
if(p[x]==x)return x;
return p[x]=find(p[x]);
}
void merge(ll x,ll y){
x=find(x),y=find(y);if(x==y)return;p[x]=y;
}
void tarjan(ll x){
vis[x]=1;
for(int i=head[x];i!=0;i=nxt[i]){
ll y=to[i];
if(!vis[y])continue;
res[(i+1)/2]=find(y);
}
for(int i=0;i<f[x].size();i++){
ll y=f[x][i];
if(vis[y])continue;
tarjan(y);
merge(y,x);
}
}
int main(){
//freopen("P1429_6.in","r",stdin);
//freopen("match.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>q>>s;
for(int i=1;i<=n;i++)p[i]=i;
for(int i=1;i<=n-1;i++){
ll u,v;
cin>>u>>v;
f[u].pb(v);
f[v].pb(u);
}
for(int i=1;i<=q;i++){
ll u,v;
cin>>u>>v;
add_req(u,v);
}
tarjan(s);
for(int i=1;i<=n;i++){
cout<<res[i]<<"\n";
}
return 0;
}
```