fork download
copy 
  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
comments (?)
stdin
copy 
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
copy 
Standard output is empty
https://ideone.com/pzVUMC
language:
Java (12.0.1)
created:
8 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!