Guest User

Untitled

a guest
Jul 31st, 2020
1,499
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.87 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. //#pragma GCC optimize("Ofast")
  3. //#pragma GCC target("avx,avx2,fma")
  4. //#pragma GCC optimization ("unroll-loops")
  5.  
  6. #define int long long
  7. #define pb push_back
  8. #define all(s) s.begin(),s.end()
  9. #define pii pair<int,int>
  10. #define fr first
  11. #define sc second
  12. #define bst ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  13. #define endl "\n"
  14. #define no cout << "NO" << endl;
  15. #define yes cout << "YES" << endl;
  16.  
  17. using namespace std;
  18.  
  19. const int N = 5e5 + 10, mod = 1e9 + 7, inf = 1e18 + 7, logn = 23;
  20. const double pi = acos(-1);
  21.  
  22. vector<int> gr[N], order, ans;
  23. int tin[N], tout[N], timer, up[N][logn], dep[N];
  24.  
  25. void dfs(int v, int pr = 1, int go = 0) {
  26. dep[v] = go;
  27. tin[v] = timer++;
  28. up[v][0] = pr;
  29.  
  30. for(int i = 1; i < logn; i++) {
  31. up[v][i] = up[up[v][i - 1]][i - 1];
  32. }
  33. for(auto it: gr[v]) {
  34. if(it != pr) {
  35. dfs(it, v, go + 1);
  36. }
  37. }
  38. tout[v] = timer++;
  39. }
  40.  
  41. bool upper(int a, int b) {
  42. return tin[a] <= tin[b] && tout[a] >= tout[b];
  43. }
  44.  
  45. int lca(int a, int b) {
  46. if(upper(a, b)) return a;
  47. if(upper(b, a)) return b;
  48.  
  49. for(int i = logn - 1; i >= 0; i--) {
  50. if(!upper(up[a][i], b)) {
  51. a = up[a][i];
  52. }
  53. }
  54. return up[a][0];
  55. }
  56.  
  57. int len(int a, int b) {
  58. return dep[a] + dep[b] - 2 * dep[lca(a, b)];
  59. }
  60.  
  61. void vpb(vector<int> &f, vector<int> &ar) {
  62. for(auto it: ar) {
  63. f.pb(it);
  64. }
  65. }
  66.  
  67. void solve() {
  68. //soln
  69. int n, fine = 1;
  70. cin >> n;
  71. for(int i = 1; i < n; i++) {
  72. int l, r;
  73. cin >> l >> r;
  74. gr[l].pb(r);
  75. gr[r].pb(l);
  76. }
  77. int cnt = 0;
  78. for(int i = 2; i <= n; i++) {
  79. cnt += (gr[i].size() == 1);
  80. }
  81. order.pb(1);
  82. for(int i = 0; i < cnt; i++) {
  83. int tmp;
  84. cin >> tmp;
  85. order.pb(tmp);
  86. }
  87. order.pb(1);
  88. dfs(1);
  89. int sum = 0;
  90. for(int i = 1; i < order.size(); i++) {
  91. sum += len(order[i], order[i - 1]);
  92. }
  93. if(sum != 2 * n - 2) {
  94. fine = 0;
  95. }
  96.  
  97. if(!fine) {
  98. cout << -1 << endl;
  99. } else {
  100. // create paths
  101. ans.pb(1);
  102. for(int i = 1; i < order.size(); i++) {
  103. int l = order[i - 1], r = order[i], cur;
  104. vector<int> path;
  105. if(upper(l, r)) {
  106. cur = r;
  107. while(cur != l) {
  108. path.pb(cur);
  109. cur = up[cur][0];
  110. }
  111. reverse(all(path));
  112. vpb(ans, path);
  113. continue;
  114. }
  115. if(upper(r, l)) {
  116. cur = l;
  117. while(cur != r) {
  118. cur = up[cur][0];
  119. path.pb(cur);
  120. }
  121. vpb(ans, path);
  122. continue;
  123. }
  124. int mid = lca(l, r);
  125. cur = l;
  126. while(cur != mid) {
  127. cur = up[cur][0];
  128. path.pb(cur);
  129. }
  130. vpb(ans, path);
  131. path.clear();
  132. cur = r;
  133. while(cur != mid) {
  134. path.pb(cur);
  135. cur = up[cur][0];
  136. }
  137. reverse(all(path));
  138. vpb(ans, path);
  139. }
  140. for(auto it: ans) {
  141. cout << it << " ";
  142. }
  143. cout << endl;
  144. }
  145. }
  146. main() {
  147. int t = 1;
  148. //cin >> t;
  149. while(t--) {
  150. solve();
  151. }
  152. }
  153.  
Advertisement
Add Comment
Please, Sign In to add comment