fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. vector<vector<int>> up;
  6. int timer, max_l;
  7. void dfs(int v, int p, vector<int> & tin, vector<int> & tout, vector<vector<int>> & g){
  8. 	up[v][0]=p;
  9. 	tin[v]=timer++;
  10. 	for(int i=1; i<=max_l; i++){
  11. 		up[v][i]=up[up[v][i-1]][i-1];
  12. 	}
  13. 	for(int i=0; i<g[v].size(); i++){
  14. 		if(g[v][i]!=p){
  15. 			dfs(g[v][i], v, tin, tout, g);
  16. 		}
  17. 	}
  18. 	tout[v]=timer;
  19. }
  20.  
  21. bool upper(int a, int b, vector<int> & tin, vector<int> & tout){
  22. 	if(tin[a]<=tin[b] and tout[a]>=tout[b]){
  23. 		return true;
  24. 	}
  25. 	return false;
  26. }
  27.  
  28. int lca(int a, int b, vector<int> & tin, vector<int> & tout){
  29. 	if(upper(a, b, tin, tout)) return a;
  30. 	if(upper(b, a, tin, tout)) return b;
  31. 	for(int i=max_l; i>=0; i--){
  32. 		if(!upper(up[a][i], b, tin, tout)){
  33. 			a=up[a][i];
  34. 		}
  35. 	}
  36. 	return up[a][0];
  37. }
  38.  
  39. int lca_dist(int a, int b, vector<int> & tin, vector<int> & tout){
  40. 	int ans=0;
  41. 	for(int i=max_l; i>=0; i--){
  42. 		if(!upper(up[a][i], b, tin, tout)){
  43. 			a=up[a][i];
  44. 			ans+=(1<<i);
  45. 		}
  46. 	}
  47. 	ans++;
  48. 	return ans;
  49. }
  50.  
  51.  
  52. int find_dist(int a, int b, vector<int> & tin, vector<int> & tout){
  53. 	int dist=0;
  54. 	int lc = lca(a, b, tin, tout);
  55. 	if(a==b){
  56. 		dist=0;
  57. 	}
  58. 	else if(lc==a){
  59. 		dist+=lca_dist(b, a, tin, tout);
  60. 	}
  61. 	else if(lc==b){
  62. 		dist+=lca_dist(a, b, tin, tout);
  63. 	}
  64. 	else{
  65. 		dist+=lca_dist(a, lc, tin, tout);
  66. 		dist+=lca_dist(b, lc, tin, tout);
  67. 	}
  68. 	return dist;
  69. }
  70.  
  71. int main() {
  72. 	ios_base::sync_with_stdio(false);
  73. 	cin.tie(0);
  74. 	cout.tie(0);
  75. 	int n;
  76. 	cin >> n;
  77. 	vector<vector<int>> g(n);
  78. 	for(int i=0; i<n-1; i++){
  79. 		int u, v;
  80. 		cin >> u >> v;
  81. 		u--;
  82. 		v--;
  83. 		g[u].push_back(v);
  84. 		g[v].push_back(u);
  85. 	}
  86. 	vector<int> tin(n, 0);
  87. 	vector<int> tout(n, 0);
  88. 	max_l=1;
  89. 	timer=0;
  90. 	while((1<<max_l)<=n) max_l++;
  91. 	up.resize(n);
  92. 	for(int i=0; i<n; i++){
  93. 		up[i].resize(max_l+1, 0);
  94. 	}
  95. 	dfs(0, 0, tin, tout, g);
  96. 	int q;
  97. 	cin >> q;
  98. 	while(q--){
  99. 		int x, y, a, b, k;
  100. 		cin >> x >> y >> a >> b >> k;
  101. 		a--;
  102. 		b--;
  103. 		x--;
  104. 		y--;
  105. 		int dist = find_dist(a, b, tin, tout);
  106. 		if(dist<=k and dist%2==k%2){
  107. 			cout << "YES\n";
  108. 			continue;
  109. 		}
  110. 		dist = find_dist(a, x, tin, tout)+find_dist(b, y, tin, tout)+1;
  111. 		if(dist<=k and dist%2==k%2){
  112. 			cout << "YES\n";
  113. 			continue;
  114. 		}
  115. 		dist = find_dist(a, y, tin, tout)+find_dist(b, x, tin, tout)+1;
  116. 		if(dist<=k and dist%2==k%2){
  117. 			cout << "YES\n";
  118. 			continue;
  119. 		}
  120. 		cout << "NO\n";
  121. 	}
  122. 	return 0;
  123. }
Success #stdin #stdout 0s 4284KB
comments (?)
stdin
copy 
5
1 2
2 3
3 4
4 5
5
1 3 1 2 2
1 4 1 3 2
1 4 1 3 3
4 2 3 3 9
5 2 3 3 9
stdout
copy 
YES
YES
NO
YES
NO
https://ideone.com/zJ6u6c
language:
C++14 (gcc 8.3)
created:
4 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!