fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define pb push_back
  3. #define fi first
  4. #define se second
  5. #define pai pair<int, int>
  6. using namespace std;
  7. const int maxN = 1e6 + 20;
  8. int n, m;
  9. vector<int> adj[maxN];
  10. int parent[maxN];
  11. pai tv[maxN];
  12. int in[maxN], out[maxN], timer;
  13. void dfs(int u = 1, int par = -1)
  14. {
  15. 	parent[u] = par;
  16. 	in[u] = ++timer;
  17.  
  18. 	for(auto v:adj[u])
  19. 		if(v != par) dfs(v, u);
  20. 	out[u] = timer;
  21. }
  22.  
  23. int deg[maxN];
  24.  
  25. void init()
  26. {
  27. 	cin >> n >> m;
  28. 	for(int i = 1; i < n; i++)
  29. 	{
  30. 		int u ,v;
  31. 		cin >> u >> v;
  32. 		adj[u].pb(v);
  33. 		adj[v].pb(u);
  34. 	}
  35.  
  36. 	dfs();
  37.  
  38. 	for(int i = 1; i <= m; i++)
  39. 	{
  40. 		int u, v;
  41. 		cin >> u >> v;
  42. 		tv[i] = {u,v};
  43. 	}
  44. }
  45.  
  46. vector<int> adj_2[maxN];
  47. int vst[maxN];
  48. bool dfs_cycle(int u)
  49. {
  50.     vst[u] = 1;
  51.     for(int v : adj_2[u]) {
  52.         if(vst[v] == 0) {
  53.             if(dfs_cycle(v)) return true;
  54.         } else if(vst[v] == 1) {
  55.             return true;
  56.         }
  57.     }
  58.     vst[u] = 2;
  59.     return false;
  60. }
  61.  
  62. bool ck() {
  63.     for(int i = 1; i <= m; i++) {
  64.         int u = tv[i].fi;
  65.         int v = tv[i].se;
  66.         adj_2[v].push_back(u);
  67.     }
  68.     fill(vst, vst + n + 1, 0);
  69.     for(int i = 1; i <= n; i++)
  70.         if(vst[i] == 0 && dfs_cycle(i)) return true;
  71.     return false;
  72. }
  73. void solve()
  74. {
  75. 	if(ck())
  76. 	{
  77. 		for(int i = 1; i <= n; i++)
  78. 			cout << 0 << '\n';
  79. 		return;
  80. 	}
  81.  
  82. 	for(int i = 1; i <= m; i++)
  83. 	{
  84. 		int u, v;
  85. 		u = tv[i].fi;
  86. 		v = tv[i].se;
  87. 		if(in[v] <= in[u] && out[u] <= out[v])
  88. 		{
  89. 			deg[in[u]]++;
  90. 			deg[out[u] + 1]--;
  91. 		}
  92. 		else if(in[u] <= in[v] && out[v] <= out[u])
  93. 		{
  94. 			int node = v;
  95. 			for(auto child:adj[u])
  96. 				if(child != parent[u])
  97. 					if(in[child] <= in[v] && out[v] <= out[child])
  98. 					{
  99. 						node = child;
  100. 						break;
  101. 					}
  102.  
  103. 			deg[1]++;
  104. 			deg[in[node]]--;
  105. 			deg[out[node]+1]++;
  106. 		}
  107. 		else
  108. 		{
  109. 			deg[in[u]]++;
  110. 			deg[out[u] + 1]--;
  111. 		}
  112. 	}
  113. 	for(int i = 1; i <= n; i++)
  114. 		deg[i] += deg[i-1];
  115. 	for(int i = 1; i <= n; i++)
  116. 		cout << (deg[in[i]] == 0) << '\n';
  117. }
  118.  
  119. int main()
  120. {
  121. 	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  122. 	init();
  123. 	solve();
  124. }
Success #stdin #stdout 0.02s 58984KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/V5cpoh
language:
C++14 (gcc 8.3)
created:
4 days 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!