fork download
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. public class TaskC_slow {
  5. private final InputReader reader;
  6. private final OutputWriter writer;
  7.  
  8. public TaskC_slow(InputReader reader, OutputWriter writer) {
  9. this.reader = reader;
  10. this.writer = writer;
  11. }
  12.  
  13. public static void main(String[] args) {
  14. InputReader reader = new InputReader(System.in);
  15. OutputWriter writer = new OutputWriter(System.out);
  16. new TaskC_slow(reader, writer).run();
  17. writer.writer.flush();
  18. }
  19.  
  20. List<Integer>[] E;
  21. int lgn;
  22. final int K = 10;
  23. final int inf = 1000 * 1000 * 1000 + 42;
  24. int[][][] upVal;
  25. int[][] up;
  26. int[] tmp;
  27. void merge(int[] a, int[] b, int[] c) {
  28. for (int i = 0; i < a.length; i++)
  29. tmp[i] = a[i];
  30. for (int i = 0; i < b.length; i++)
  31. tmp[i + a.length] = b[i];
  32. Arrays.sort(tmp);
  33. int pt = 0;
  34. Arrays.fill(c, inf);
  35. for (int i = 0; i < tmp.length && pt < c.length; i++)
  36. if (pt == 0 || tmp[i] != c[pt - 1])
  37. c[pt++] = tmp[i];
  38. }
  39.  
  40. int[] D;
  41.  
  42. void DFS(int x, int p) {
  43. up[0][x] = p;
  44. D[x] = D[p] + 1;
  45. for (int l = 1; l <= lgn; l++) {
  46. up[l][x] = up[l - 1][up[l - 1][x]];
  47. merge(upVal[l - 1][x], upVal[l - 1][up[l - 1][x]], upVal[l][x]);
  48. }
  49. for (int i = 0; i < E[x].size(); i++) {
  50. int y = E[x].get(i);
  51. if (y == p) {
  52. E[x].remove(i);
  53. --i;
  54. continue;
  55. }
  56. DFS(y, x);
  57. }
  58. }
  59.  
  60. int lca(int a, int b) {
  61. if (D[a] > D[b]) {
  62. int t = a;
  63. a = b;
  64. b = t;
  65. }
  66. for (int l = lgn; l >= 0; l--)
  67. if (D[b] - D[a] >= (1 << l))
  68. b = up[l][b];
  69. if (a == b)
  70. return a;
  71. for (int l = lgn; l >= 0; l--)
  72. if (up[l][a] != up[l][b]) {
  73. a = up[l][a];
  74. b = up[l][b];
  75. }
  76. a = up[0][a];
  77. return a;
  78. }
  79.  
  80. public void run() {
  81. int n = reader.nextInt();
  82. int m = reader.nextInt();
  83. int q = reader.nextInt();
  84. E = new ArrayList[n];
  85. for (int i = 0; i < n; i++)
  86. E[i] = new ArrayList<Integer>();
  87. for (int i = 0; i < n - 1; i++) {
  88. int a = reader.nextInt() - 1;
  89. int b = reader.nextInt() - 1;
  90. E[a].add(b);
  91. E[b].add(a);
  92. }
  93. lgn = 0;
  94. while ((1 << (lgn + 1)) <= n)
  95. lgn++;
  96. upVal = new int[lgn + 1][n][K];
  97. for (int x = 0; x < n; x++)
  98. Arrays.fill(upVal[0][x], inf);
  99. up = new int[lgn + 1][n];
  100. tmp = new int[2 * K];
  101. D = new int[n];
  102. int[] res = new int[K];
  103. Arrays.fill(res, inf);
  104. for (int i = 0; i < m; i++) {
  105. int t = reader.nextInt() - 1;
  106. res[0] = i;
  107. merge(res, upVal[0][t], upVal[0][t]);
  108. }
  109. DFS(0, 0);
  110. for (int i = 0; i < q; i++) {
  111. int a = reader.nextInt() - 1;
  112. int b = reader.nextInt() - 1;
  113. int c = reader.nextInt();
  114. int x = lca(a, b);
  115. Arrays.fill(res, inf);
  116. for (int l = lgn; l >= 0; l--) {
  117. if (D[a] - (1 << l) >= D[x] - 1) {
  118. merge(upVal[l][a], res, res);
  119. a = up[l][a];
  120. }
  121. if (D[b] - (1 << l) >= D[x] - 1) {
  122. merge(upVal[l][b], res, res);
  123. b = up[l][b];
  124. }
  125. }
  126. int cnt = 0;
  127. while (cnt < res.length && res[cnt] != inf)
  128. cnt++;
  129. cnt = Math.min(cnt, c);
  130. writer.printf("%d", cnt);
  131. for (int j = 0; j < cnt; j++)
  132. writer.printf(" %d", res[j] + 1);
  133. writer.printf("\n");
  134. }
  135. }
  136.  
  137.  
  138. static class InputReader {
  139. public BufferedReader reader;
  140. public StringTokenizer tokenizer;
  141.  
  142. public InputReader(InputStream stream) {
  143. reader = new BufferedReader(new InputStreamReader(stream), 32768);
  144. tokenizer = null;
  145. }
  146.  
  147. public String next() {
  148. while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  149. try {
  150. tokenizer = new StringTokenizer(reader.readLine());
  151. } catch (IOException e) {
  152. throw new RuntimeException(e);
  153. }
  154. }
  155. return tokenizer.nextToken();
  156. }
  157.  
  158. public int nextInt() {
  159. return Integer.parseInt(next());
  160. }
  161.  
  162. public double nextDouble() {
  163. return Double.parseDouble(next());
  164. }
  165.  
  166. public long nextLong() {
  167. return Long.parseLong(next());
  168. }
  169. }
  170.  
  171. static class OutputWriter {
  172. public PrintWriter writer;
  173.  
  174. OutputWriter(OutputStream stream) {
  175. writer = new PrintWriter(stream);
  176. }
  177.  
  178. public void printf(String format, Object... args) {
  179. writer.print(String.format(Locale.ENGLISH, format, args));
  180. }
  181. }
  182. }
  183.  
  184.  
Compilation error #stdin compilation error #stdout 0s 0KB
stdin
Standard input is empty
compilation info
Main.java:4: error: class TaskC_slow is public, should be declared in a file named TaskC_slow.java
public class TaskC_slow {
       ^
Note: Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
1 error
stdout
Standard output is empty