Lca 入门题
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <cmath> #include <queue> #include <vector> #include <map> using namespace std; int const MAXN = 10010; int n,u,v; vector <int> q[MAXN]; int father[MAXN],vis[MAXN],root[MAXN]; void Init(){ for(int i = 0;i < MAXN;i++){ q[i].clear(); vis[i] = 0; root[i] = 1; father[i] = i; } } int Find(int x){ int y = x; while(y != father[y]){ y = father[y]; } while(x != father[x]){ int temp = father[x]; father[x] = y; x = temp; } return x; } void Union(int x,int y){ int xx = Find(x); int yy = Find(y); if(xx == yy) return ; father[yy] = xx; } void Lca(int per){ for(int i = 0;i < q[per].size();i++){ Lca(q[per][i]); Union(per,q[per][i]); } vis[per] = 1; if(per == u && vis[v] == 1){ printf("%d\n",Find(v)); return ; } if(per == v && vis[u] == 1){ printf("%d\n",Find(u)); return ; } } int main(){ int t; while(~scanf("%d",&t)){ while(t--){ Init(); int n; scanf("%d",&n); for(int i = 1;i < n;i++){ int a,b; scanf("%d%d",&a,&b); q[a].push_back(b); root[b] = 0; } scanf("%d%d",&u,&v); int s; for(int i = 1;i <= n;i++){ if(root[i]){ s = i; break; } } Lca(s); } } return 0; } /* 2 5 2 3 3 4 3 1 1 5 3 5 */