fork(3) download
copy 
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cstring>
  4. #include <vector>
  5. using namespace std;
  6. const int MAX = 100005;
  7. const int LG = 17;
  8. vector<int> adj[MAX];
  9. struct node
  10. {
  11. 	int a[11];
  12. 	node()
  13. 	{
  14. 		memset(a, 63, sizeof(a));
  15. 	}
  16. 	void insert(int val)
  17. 	{
  18. 		a[10] = val;
  19. 		sort(a, a + 11);
  20. 	}
  21. } vals[LG][MAX];
  22. node merge(node x, node y)
  23. {
  24. 	node ans = x;
  25. 	for (int i = 0; i < 11; i++)
  26. 		ans.insert(y.a[i]);
  27. 	return ans;
  28. }
  29. int par[LG][MAX], d[MAX];
  30. void dfs(int p, int v)
  31. {
  32. 	par[0][v] = p;
  33. 	for (int i = 1; i < LG; i++)
  34. 	{
  35. 		par[i][v] = par[i - 1][par[i - 1][v]];
  36. 		vals[i][v] = merge(vals[i - 1][v], vals[i - 1][par[i - 1][v]]);
  37. 	}
  38. 	for (int i = 0; i < (int)adj[v].size(); i++)
  39. 	{
  40. 		int u = adj[v][i];
  41. 		if (u != p)
  42. 		{
  43. 			d[u] = d[v] + 1;
  44. 			dfs(v, u);
  45. 		}
  46. 	}
  47. }
  48. int get_parent(int v, int k)
  49. {
  50. 	for (int i = 0; i < LG; i++)
  51. 		if ((1 << i) & k)
  52. 			v = par[i][v];
  53. 	return v;
  54. }
  55. int lca(int u, int v)
  56. {
  57. 	if (d[u] < d[v])
  58. 		swap(u, v);
  59. 	u = get_parent(u, d[u] - d[v]);
  60. 	if (u == v)
  61. 		return u;
  62. 	for (int i = LG - 1; i >= 0; i--)
  63. 		if (par[i][u] != par[i][v])
  64. 		{
  65. 			u = par[i][u];
  66. 			v = par[i][v];
  67. 		}
  68. 	return par[0][v];
  69. }
  70. node get(int v, int k)
  71. {
  72. 	node ans;
  73. 	for (int i = 0; i < LG; i++)
  74. 		if ((1 << i) & k)
  75. 		{
  76. 			ans = merge(ans, vals[i][v]);
  77. 			v = par[i][v];
  78. 		}
  79. 	return ans;
  80. }
  81. int main()
  82. {
  83. 	ios::sync_with_stdio(false);
  84. 	cin.tie(0);
  85. 	int n, m, q;
  86. 	cin >> n >> m >> q;
  87. 	for (int i = 0; i < n - 1; i++)
  88. 	{
  89. 		int u, v;
  90. 		cin >> u >> v;
  91. 		u--;
  92. 		v--;
  93. 		adj[u].push_back(v);
  94. 		adj[v].push_back(u);
  95. 	}
  96. 	for (int i = 0; i < m; i++)
  97. 	{
  98. 		int c;
  99. 		cin >> c;
  100. 		c--;
  101. 		vals[0][c].insert(i);
  102. 	}
  103. 	dfs(0, 0);
  104. 	while (q--)
  105. 	{
  106. 		int u, v, k;
  107. 		cin >> u >> v >> k;
  108. 		u--;
  109. 		v--;
  110. 		int p = lca(u, v);
  111. 		node x = get(u, d[u] - d[p]);
  112. 		node y = get(v, d[v] - d[p] + 1);
  113. 		node ans = merge(x, y);
  114. 		int tmp = 0;
  115. 		while (tmp < k && ans.a[tmp] < m)
  116. 			tmp++;
  117. 		k = tmp;
  118. 		cout << k;
  119. 		for (int i = 0; i < k; i++)
  120. 			cout << " " << ans.a[i] + 1;
  121. 		cout << "\n";
  122. 	}
  123. 	return 0;
  124. }
  125.  
Runtime error #stdin #stdout 0.05s 84736KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/1NqglU
language:
C++14 (gcc 8.3)
created:
9 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!