[CodeUp 4035] 커피전문점

[CodeUp 4035] 커피전문점

#include using namespace std; const int N=1e5+1; vector ad[N]; int dep[N],par[N][17]; void make_tree(int cur,int prv) { for(auto nxt : ad[cur]){ if(nxt==prv) continue; dep[nxt]=dep[cur]+1, par[nxt][0]=cur; make_tree(nxt,cur); } } int lca(int u,int v) { if(dep[u]=0;i--) if(par[u][i]!=par[v][i]) u=par[u][i], v=par[v][i]; return par[u][0]; } int main() { ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int n; cin >> n; for(int i=1;i> u >> v; ad[u].push_back(v); ad[v].push_back(u); } int a,b,c; cin >> a >> b >> c; make_tree(a,0); for(int j=1;j<17;j++) for(int i=1;i<=n;i++) par[i][j]=par[par[i][j-1]][j-1]; cout << dep[b]+dep[c]-dep[lca(b,c)]+1 << '

'; int q; cin >> q; while(q--){ int v; cin >> v; int x=lca(v,b), y=lca(v,c); if(dep[x]

'; } }

from http://heejayaa.tistory.com/91 by ccl(A) rewrite - 2021-08-01 02:26:33