fork download
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. typedef vector<int> vi;
  6. typedef vector<ll> vl;
  7.  
  8. #define INF (int)1e9
  9.  
  10. int n, father[10005], depth[10005], dp[10005][20];
  11. vector<int> child[10005];
  12.  
  13. void dfs(int cur, int par, int dep){
  14. father[cur] = par;
  15. depth[cur] = dep;
  16. for(int i = 0; i < child[cur].size(); i++){
  17. int next = child[cur][i];
  18. dfs(next, cur, dep+1);
  19. }
  20. }
  21.  
  22. void precompute(){
  23. for(int i = 0; i < 10005; i++){
  24. for(int j = 0; j < 20; j++){
  25. dp[i][j] = 1;
  26. }
  27. }
  28. for(int i = 1; i <= n; i++){
  29. dp[i][0] = father[i];
  30. }
  31. for(int p = 1; p <= 15; p++){
  32. for(int cur = 1; cur <= n; cur++){
  33. dp[cur][p] = dp[dp[cur][p-1]][p-1];
  34. }
  35. }
  36. }
  37.  
  38. int lca(int a, int b){
  39. if(depth[a] > depth[b]){
  40. swap(a, b);
  41. }
  42. int dif = depth[b] - depth[a];
  43. for(int p = 15; p >= 0; p--){
  44. if( (1 << p) <= dif ){
  45. b = dp[b][p];
  46. dif -= (1 << p);
  47. }
  48. }
  49. if(a == b){
  50. return a;
  51. }
  52. for(int p = 15; p >= 0; p--){
  53. if( dp[b][p] != dp[a][p] ){
  54. a = dp[a][p];
  55. b = dp[b][p];
  56. }
  57. }
  58. return father[a];
  59. }
  60.  
  61. int main(){
  62. int t;
  63. cin >> t;
  64. for(int test = 1; test <= t; test++){
  65. cout << "Case " << t << ":" << endl;
  66. cin >> n;
  67. int m, temp;
  68. for(int i = 1; i <= n; i++){
  69. cin >> m;
  70. for(int j = 1; j <= m; j++){
  71. cin >> temp;
  72. child[i].push_back(temp);
  73. }
  74. }
  75. dfs(1, 1, 0);
  76. precompute();
  77.  
  78. int q, a, b;
  79. cin >> q;
  80. for(int i = 1; i <= q; i++){
  81. cin >> a >> b;
  82. cout << lca(a, b) << endl;
  83. }
  84. for(int i = 1; i <= n; i++){
  85. child[i].clear();
  86. father[i] = 0;
  87. depth[i] = 0;
  88. }
  89.  
  90. }
  91. }
Success #stdin #stdout 0s 4696KB
stdin
Standard input is empty
stdout
Case 1: