fork(1) download 
  1.  
  2.  
  3. import java.io.IOException;
  4. import java.io.InputStream;
  5. import java.util.*;
  6.  
  7. class TestClass {
  8.  
  9.  
  10.     static final class InputReader {
  11.         private final InputStream stream;
  12.         private final byte[] buf = new byte[1024];
  13.         private int curChar;
  14.         private int numChars;
  15.  
  16.         public InputReader(InputStream stream) {
  17.             this.stream = stream;
  18.         }
  19.  
  20.         private int read() throws IOException {
  21.             if (curChar >= numChars) {
  22.                 curChar = 0;
  23.                 numChars = stream.read(buf);
  24.                 if (numChars <= 0) {
  25.                     return -1;
  26.                 }
  27.             }
  28.             return buf[curChar++];
  29.         }
  30.  
  31.         public final int readInt() throws IOException {
  32.             return (int) readLong();
  33.         }
  34.  
  35.         public final long readLong() throws IOException {
  36.             int c = read();
  37.             while (isSpaceChar(c)) {
  38.                 c = read();
  39.                 if (c == -1) throw new IOException();
  40.             }
  41.             boolean negative = false;
  42.             if (c == '-') {
  43.                 negative = true;
  44.                 c = read();
  45.             }
  46.             long res = 0;
  47.             do {
  48.                 res *= 10;
  49.                 res += c - '0';
  50.                 c = read();
  51.             } while (!isSpaceChar(c));
  52.             return negative ? -res : res;
  53.         }
  54.  
  55.         public final int[] readIntArray(int size) throws IOException {
  56.             int[] array = new int[size];
  57.             for (int i = 0; i < size; i++) {
  58.                 array[i] = readInt();
  59.             }
  60.             return array;
  61.         }
  62.  
  63.         public final long[] readLongArray(int size) throws IOException {
  64.             long[] array = new long[size];
  65.             for (int i = 0; i < size; i++) {
  66.                 array[i] = readLong();
  67.             }
  68.             return array;
  69.         }
  70.  
  71.         public final String readString() throws IOException {
  72.             int c = read();
  73.             while (isSpaceChar(c)) {
  74.                 c = read();
  75.             }
  76.             StringBuilder res = new StringBuilder();
  77.             do {
  78.                 res.append((char) c);
  79.                 c = read();
  80.             } while (!isSpaceChar(c));
  81.             return res.toString();
  82.         }
  83.  
  84.         private boolean isSpaceChar(int c) {
  85.             return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  86.         }
  87.     }
  88.  
  89.     static long mulmod(long a, long b,
  90.                        long mod) {
  91.         long res = 0; // Initialize result
  92.         a = a % mod;
  93.         while (b > 0) {
  94.             // If b is odd, add 'a' to result
  95.             if (b % 2 == 1) {
  96.                 res = (res + a) % mod;
  97.             }
  98.  
  99.             // Multiply 'a' with 2
  100.             a = (a * 2) % mod;
  101.  
  102.             // Divide b by 2
  103.             b /= 2;
  104.         }
  105.  
  106.         // Return result
  107.         return res % mod;
  108.     }
  109.  
  110.     static long pow(long a, long b, long MOD) {
  111.         long x = 1, y = a;
  112.         while (b > 0) {
  113.             if (b % 2 == 1) {
  114.                 x = (x * y);
  115.                 if (x > MOD) x %= MOD;
  116.             }
  117.             y = (y * y);
  118.             if (y > MOD) y %= MOD;
  119.             b /= 2;
  120.         }
  121.         return x;
  122.     }
  123.  
  124.     static long[] f = new long[100001];
  125.  
  126.     static long InverseEuler(long n, long MOD) {
  127.         return pow(n, MOD - 2, MOD);
  128.     }
  129.  
  130.     static long C(int n, int r, long MOD) {
  131.  
  132.         return (f[n] * ((InverseEuler(f[r], MOD) * InverseEuler(f[n - r], MOD)) % MOD)) % MOD;
  133.     }
  134.  
  135.     public static class SegmentTree {
  136.         long[] tree;
  137.         long[] lazy;
  138.         int n;
  139.  
  140.         public SegmentTree(long[] arr) {
  141.             n = arr.length;
  142.             tree = new long[arr.length * 5];
  143.             lazy = new long[arr.length * 5];
  144.             build(arr, 0, arr.length - 1, 0);
  145.         }
  146.  
  147.         private void build(long[] arr, int s, int e, int pos) {
  148.             if (s == e) {
  149.                 tree[pos] = arr[s];
  150.                 return;
  151.             }
  152.             int m = (s + e) / 2;
  153.  
  154.             build(arr, s, m, 2 * pos + 1);
  155.             build(arr, m + 1, e, 2 * pos + 2);
  156.  
  157.             tree[pos] = Math.max(tree[2 * pos + 1], tree[2 * pos + 2]);
  158.         }
  159.  
  160.         public void update(int s, int e, long val) {
  161.             updateUtil(s, e, val, 0, n - 1, 0);
  162.         }
  163.  
  164.         public long get(int s, int e) {
  165.             return getUtil(s, e, 0, n - 1, 0);
  166.         }
  167.  
  168.         private long getUtil(int gs, int ge, int s, int e, int pos) {
  169.             if (s > e || s > ge || e < gs) return Long.MIN_VALUE;
  170.             if (lazy[pos] != 0) {
  171.                 tree[pos] += lazy[pos];
  172.                 if (s != e) {
  173.                     lazy[2 * pos + 1] += lazy[pos];
  174.                     lazy[2 * pos + 2] += lazy[pos];
  175.                 }
  176.                 lazy[pos] = 0;
  177.             }
  178.             if (s >= gs && e <= ge) {
  179.                 return tree[pos];
  180.             }
  181.             int m = (s + e) / 2;
  182.             return Math.max(getUtil(gs, ge, s, m, 2 * pos + 1), getUtil(gs, ge, m + 1, e, 2 * pos + 2));
  183.         }
  184.  
  185.         private void updateUtil(int us, int ue, long val, int s, int e, int pos) {
  186.             if (s > e || s > ue || e < us) return;
  187.  
  188.             if (lazy[pos] != 0) {
  189.                 tree[pos] += lazy[pos];
  190.                 if (s != e) {
  191.                     lazy[2 * pos + 1] += lazy[pos];
  192.                     lazy[2 * pos + 2] += lazy[pos];
  193.                 }
  194.                 lazy[pos] = 0;
  195.             }
  196.  
  197.             if (s >= us && e <= ue) {
  198.                 tree[pos] += val;
  199.                 if (s != e) {
  200.                     lazy[2 * pos + 1] += val;
  201.                     lazy[2 * pos + 2] += val;
  202.                 }
  203.                 return;
  204.             }
  205.  
  206.             int m = (s + e) / 2;
  207.             updateUtil(us, ue, val, s, m, 2 * pos + 1);
  208.             updateUtil(us, ue, val, m + 1, e, 2 * pos + 2);
  209.  
  210.             tree[pos] = Math.max(tree[2 * pos + 1], tree[2 * pos + 2]);
  211.         }
  212.  
  213.  
  214.     }
  215.  
  216.  
  217.     static int[] h = {0, 0, -1, 1};
  218.     static int[] v = {1, -1, 0, 0};
  219.  
  220.  
  221.     public static class Pair {
  222.         public int x, y, p;
  223.  
  224.         public Pair(int d, int y) {
  225.             this.x = d;
  226.             this.y = y;
  227.         }
  228.  
  229.  
  230.     }
  231.  
  232.     static long compute_hash(String s) {
  233.         int p = 31;
  234.         int m = 1000000007;
  235.         long hash_value = 0;
  236.         long p_pow = 1;
  237.         for (int i = 0; i < s.length(); ++i) {
  238.             char c = s.charAt(i);
  239.             hash_value = (hash_value + (c - 'a' + 1) * p_pow) % m;
  240.             p_pow = (p_pow * p) % m;
  241.         }
  242.         return hash_value;
  243.     }
  244.  
  245.     static int counter = 0;
  246.  
  247.     public static void main(String[] args) throws Exception {
  248.         //https://i...content-available-to-author-only...e.com/ebRGa6
  249.         InputReader in = new InputReader(System.in);
  250.         long t = in.readLong();
  251.  
  252.             int[][] pre = new int[100000+1][17];
  253.             int[] tin = new int[100000+1];
  254.             int[] tout = new int[100000+1];
  255.             int[] xors = new int[100000+1];
  256.         while (t-- > 0) {
  257.             counter = 0;
  258.             int n = in.readInt();
  259.             int q = in.readInt();
  260.  
  261.             int[] val = new int[n+1];
  262.             for (int i = 1; i <= n; ++i) {
  263.                 val[i] = in.readInt();
  264.             }
  265.  
  266.             List<List<Integer>> tree = new ArrayList<>();
  267.             for (int i = 0; i <= n; ++i) {
  268.                 tree.add(new ArrayList<>());
  269.                 Arrays.fill(pre[i], -1);
  270.             }
  271.             for (int i = 0; i < n - 1; ++i) {
  272.                 int p = in.readInt();
  273.                 int r = in.readInt();
  274.  
  275.                 tree.get(p).add(r);
  276.                 tree.get(r ).add(p );
  277.  
  278.             }
  279.  
  280.             preprocess(1, pre, tree, new int[n+1], 0, -1, tin, tout, 0, val, xors);
  281. //            for (int i = 0; i < n; ++i) {
  282. //                for (int j = 30; j >= 0; --j) {
  283. //                    System.out.print(pre[i][j] + " ");
  284. //                }
  285. //                System.out.println("");
  286. //            }
  287.             while (q-- > 0) {
  288.                 int s = in.readInt();
  289.                 int e = in.readInt();
  290.                 if (e > s) {
  291.                     int temp = s;
  292.                     s = e;
  293.                     e = temp;
  294.                 }
  295.  
  296.                 if (s == e) {
  297.                     System.out.println(val[s]);
  298.                     continue;
  299.                 }
  300.  
  301.                 if ((tin[s] <= tin[e] && tout[s] >= tout[e])) {
  302.  
  303.                     System.out.println(xors[s] ^ xors[e] ^ val[s]);
  304.                     continue;
  305.                 }
  306.                 if ((tin[s] >= tin[e] && tout[s] <= tout[e])) {
  307.  
  308.                     System.out.println(xors[s] ^ xors[e] ^ val[e]);
  309.                     continue;
  310.                 }
  311.                 int xor = xors[s];
  312.                 for (int i = 16; i >= 0; --i) {
  313.                     if (pre[s][i] != 0) {
  314.                         if (!(tin[pre[s][i]] <= tin[e] && tout[pre[s][i]] >= tout[e])) {
  315.                             s = pre[s][i];
  316.                         }
  317.                     }
  318.                 }
  319.                 // assert(pre[s][0] != -1);
  320.                 xor = xor ^ xors[e] ^ val[pre[s][0]];
  321.                 System.out.println(xor);
  322.             }
  323.  
  324.         }
  325.  
  326.  
  327.     }
  328.  
  329.     private static void preprocess(int pos, int[][] pre, List<List<Integer>> tree, int[] traverse, int depth, int last, int[] tin, int[] tout, int xor, int[] val, int[] xors) {
  330.         tin[pos] = counter++;
  331.         xors[pos] = xor ^ val[pos];
  332.         traverse[depth] = pos;
  333.  
  334.         for (int i = 0; depth - (1 << i) >= 0; ++i) {
  335.             pre[pos][i] = traverse[depth - (1 << i)];
  336.         }
  337.  
  338.         for (int i = 0; i < tree.get(pos).size(); ++i) {
  339.             if (tree.get(pos).get(i) != last)
  340.                 preprocess(tree.get(pos).get(i), pre, tree, traverse, depth + 1, pos, tin, tout, xors[pos], val, xors);
  341.         }
  342.         tout[pos] = counter++;
  343.     }
  344.  
  345.     private static long solve(long[][] dp, int n, int r) {
  346.         if (n == 0) {
  347.             if (r == 0) return 1;
  348.             else return 0;
  349.         }
  350.         if (r <= 0) return 0;
  351.         if (dp[n][r] != -1) return dp[n][r];
  352.         long answer = 0;
  353.         for (int i = 1; i < n; ++i) {
  354.             answer += solve(dp, n - 1, r - i);
  355.         }
  356.         dp[n][r] = answer;
  357.         return answer;
  358.     }
  359.  
  360.     static int gcd(int a, int b) {
  361.  
  362.         while (b != 0) {
  363.             int t = a;
  364.             a = b;
  365.             b = t % b;
  366.         }
  367.         return a;
  368.     }
  369.  
  370.     class Solution {
  371.         public int maxProduct(int[] nums) {
  372.             PriorityQueue<Integer> p = new PriorityQueue<>(new Comparator<Integer>() {
  373.                 @Override
  374.                 public int compare(Integer integer, Integer t1) {
  375.                     return Integer.compare(t1, integer);
  376.                 }
  377.             });
  378.             for (int i = 0; i < nums.length; ++i) {
  379.                 p.add(nums[i]);
  380.             }
  381.             int f = p.remove();
  382.             int s = p.remove();
  383.             return (f - 1) * (s - 1);
  384.         }
  385.     }
  386.  
  387.     static boolean submit = true;
  388.  
  389.     static void debug(String s) {
  390.         if (!submit)
  391.             System.out.println(s);
  392.     }
  393.  
  394.     static void debug(int s) {
  395.         if (!submit)
  396.             System.out.println(s);
  397.     }
  398.  
  399. }
  400.  
  401.  
  402.  
  403.  
  404.  
  405.  
  406.  
  407.  
  408.  
  409.  
  410.  
  411.  
  412.  
  413.  
  414.  
  415.  
  416.  
  417.  
  418.  
  419.  
  420.  
  421.  
  422.  
  423.  
  424.  
  425.  
  426.  
  427.  
  428.  
  429.  
  430.  
  431.  
  432.  
  433.  
Runtime error #stdin #stdout #stderr 0.07s 43632KB
comments (?)
stdin 
1
5 2
1 2 3 4 5
1 2
1 3
2 4
2 5
3 5
4 5
stdout 
Standard output is empty
stderr 
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 100001
	at TestClass.main(Main.java:314)
https://ideone.com/KTGXUE
language:
Java (HotSpot 12)
created:
5 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!