Advertisement
Guest User

Untitled

a guest
Feb 25th, 2018
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.82 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. int n;
  6. vector<int> g[100000];
  7. int par[100000][20];
  8. int tin[100000];
  9. int tout[100000];
  10. bool used[100000];
  11. int t = 0;
  12.  
  13. void dfs(int v, int p) {
  14. tin[v] = t++;
  15. par[v][0] = p;
  16. for (int i = 1; i < 20; i++) {
  17. par[v][i] = par[par[v][i - 1]][i - 1];
  18. }
  19.  
  20. for (int to : g[v]) {
  21. if (to == p) continue;
  22. dfs(to, v);
  23. }
  24. tout[v] = t++;
  25. }
  26.  
  27. bool upper(int v1, int v2) {
  28. if (v1 == -1) return 1;
  29. else if (v2 == -1) return 0;
  30. return tin[v1] <= tin[v2] && tout[v1] >= tout[v2];
  31. }
  32.  
  33. int lca(int v1, int v2) {
  34. if (upper(v1, v2)) return v1;
  35. if (upper(v2, v1)) return v2;
  36. for (int i = 19; i >= 0; i--) {
  37. if (!upper(par[v1][i], v2)) v1 = par[v1][i];
  38. }
  39. return par[v1][0];
  40. }
  41.  
  42. vector<int> ans;
  43. vector<int> add[100000];
  44. bool done[100000];
  45. int l[100000];
  46.  
  47. vector<int> st;
  48. int up = -1;
  49.  
  50. void dfs2(int v, int p) {
  51. for (int to : g[v]) {
  52. if (to == p) continue;
  53. dfs2(to, v);
  54. }
  55.  
  56. for (int x : add[v]) {
  57. if (!used[x]) {
  58. st.push_back(x);
  59. if (up == 0) {
  60. up = l[x];
  61. } else {
  62. if (upper(up, l[x])) {
  63. up = l[x];
  64. }
  65. }
  66. }
  67. }
  68. if (v == up) {
  69. for (int x : st) {
  70. used[x] = 1;
  71. }
  72. up = -1;
  73. st.clear();
  74. ans.push_back(v);
  75. }
  76. }
  77.  
  78. int main() {
  79. ios_base::sync_with_stdio(0);
  80. for (int i = 0; i < 100000; i++) {
  81. done[i] = 0;
  82. }
  83. cin >> n;
  84. for (int i = 1; i < n; i++) {
  85. int v, to;
  86. cin >> v >> to;
  87. v--;
  88. to--;
  89. g[v].push_back(to);
  90. g[to].push_back(v);
  91. }
  92.  
  93. dfs(0, 0);
  94. int m;
  95. cin >> m;
  96.  
  97. for (int i = 0; i < m; i++) {
  98. int v1, v2;
  99. cin >> v1 >> v2;
  100. v1--;
  101. v2--;
  102. int v = lca(v1, v2);
  103. add[v1].push_back(i);
  104. add[v2].push_back(i);
  105. l[i] = v;
  106. }
  107.  
  108. dfs2(0, -1);
  109.  
  110. cout << ans.size() << "\n";
  111. for (int x : ans) {
  112. cout << x + 1 << " ";
  113. }
  114.  
  115. return 0;
  116. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement