fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int int64_t
  5. #define endl '\n'
  6. #define vi vector<int>
  7. #define vvi vector<vi>
  8. #define F0(n, i) for(int i = 0; i < n; i++)
  9. #define F1(n, i) for(int i = 1; i <= n; i++)
  10. #define each(a) for(auto& e: a)
  11. #define pb push_back
  12. #define arr(a) { each(a) cerr << e << ' '; cerr << endl; }
  13. #define mtx(m) each(m) arr(e);
  14.  
  15. void solve() {
  16. 	int n;
  17. 	cin >> n;
  18. 	vi a(n), prt(n), vis(n), tin(n), tout(n), node(n), ans(n);
  19. 	F0(n, i) cin >> a[i], node[a[i]] = i;
  20. 	vvi G(n);
  21. 	F0(n - 1, _) {
  22. 		int u, v;
  23. 		cin >> u >> v;
  24. 		G[u].pb(v);
  25. 		G[v].pb(u);
  26. 	}
  27. 	function<void(int, int)> dfs = [&](int i, int p) {
  28. 		prt[i] = p;
  29. 		each(G[i]) {
  30. 			if(e != p) dfs(e, i);
  31. 		}
  32. 	};
  33. 	mtx(G);
  34. 	dfs(0, -1);
  35. 	int t = 0;
  36. 	function<void(int)> dfs_2 = [&](int i) {
  37. 		vis[i] = 1;
  38. 		tin[i] = t++;
  39. 		each(G[i]) {
  40. 			if(!vis[e]) dfs_2(e);
  41. 		}
  42. 		tout[i] = t++;
  43. 	};
  44. 	dfs_2(0);
  45. 	int curr = node[0], mex = 0;
  46. 	while(curr != -1) {
  47. 		while(mex < n) {
  48. 			int u = node[mex];
  49. 			if(tin[u] < tin[curr] || tout[u] > tout[curr]) break ;
  50. 			mex++;
  51. 		}
  52. 		ans[curr] = mex;
  53. 		curr = prt[curr];
  54. 	}
  55. 	each(ans) cout << e << ' ';
  56. }
  57.  
  58. int32_t main() {
  59. 	int t = 1;
  60. 	cin >> t;
  61. 	while(t--) {
  62. 		solve();
  63. 		cout << endl;
  64. 		cerr << endl;
  65. 	}
  66. }
Success #stdin #stdout #stderr 0.01s 5448KB
comments (?)
stdin
copy 
2
6
4 3 5 1 0 2
0 1
1 2
0 3
3 4
3 5
3
0 1 2
0 1
0 2
stdout
copy 
6 0 0 3 1 0 
3 0 0
stderr
copy 
1 3 
0 2 
1 
0 4 5 
3 
3 

1 2 
0 
0
https://ideone.com/tfUIEn
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!