CLERVT_tester.java

import java.io.InputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
 
class TheKing
{
    static final int MAXN=100_005;
    static ArrayList<Integer>[] graph;
    static Edge[] edges;
    static int[] depth,parent;
    static int n,root;
    static Integer[] subset;
    static Comparator<Integer> com = new Comparator<Integer>()
    {
        @Override
        public int compare(Integer a, Integer b)
        {
            return Integer.compare(priority[a], priority[b]);
        }
    };
    static LCA_Sparse eu;
 
    static IO io=new IO(System.in);
 
    public static void main(String[] args)throws Exception
    {
        int i;
        n=io.nextInt();
        graph = new ArrayList[n];
        edges = new Edge[n-1];
 
        for(i=0;i<graph.length;++i)graph[i]=new ArrayList<>();
 
        for(i=0;i<n-1;++i)
        {
            int a=io.nextInt()-1,b=io.nextInt()-1;
            edges[i] = new Edge(a, b, 1);
            graph[a].add(i);    graph[b].add(i);
        }
        root = 0;
        organise();
 
        eu = new LCA_Sparse(graph, edges, depth, parent, chCount, n, root);
        preparePriority();
 
        subset = new Integer[io.nextInt()];
        for(i=0; i<subset.length; ++i)
            subset[i] = io.nextInt()-1;
        Arrays.sort(subset, com);
 
        dp = new int[1 << subset.length];
        dp[0] = n-1;
        answer = dp[len++];
 
        for(i=0; i<subset.length; ++i)
            addToDP(subset[i]);
        System.out.println(answer);
    }
 
    static int dp[], len, answer;
    static void addToDP(int node)
    {
        int curr = len, i;
        dp[len] = n - depth[node];
        answer ^= dp[len++];
 
        for(i=1; i<curr; ++i)
        {
            dp[len] = dp[i] - depth[node] + depth[eu.findLCA(subset[flLog2(i)], node)];
            answer ^= dp[len++];
        }
    }
 
    static int[] priority;
    static void preparePriority()
    {
        priority = new int[n];
        int top = 0, prior = 0, ele, conn;    queue[top++] = root;
 
        while(top > 0)
        {
            priority[ele = queue[--top]] = prior++;
            Iterator<Integer> itr = graph[ele].iterator();
            while(itr.hasNext())
            {
                conn = edges[itr.next()].getOtherVertex(ele);
                if(depth[conn] > depth[ele])
                    queue[top++] = conn;
            }
        }
    }
 
    static int[] queue=new int[MAXN],chCount;
    static void organise()
    {
        parent=new int[n];  depth=new int[n];   chCount=new int[n];
        Arrays.fill(chCount, 1);
 
        int i,st=0,end=0;
        parent[root]=-1;    depth[root]=1;
        queue[end++]=root;
        while(st<end)
        {
            int node = queue[st++], h = depth[node]+1;
            Iterator<Integer> itr = graph[node].iterator();
            while(itr.hasNext())
            {
                int ch = edges[itr.next()].getOtherVertex(node);
                if(depth[ch]>0)continue;
                depth[ch]=h;   parent[ch]=node;
                queue[end++]=ch;
            }
        }
        for(i=n-1;i>=0;--i)
            if(queue[i]!=root)
                chCount[parent[queue[i]]] += chCount[queue[i]];
    }
    static int flLog2(int num)
    {
        num |= num >> 1;
        num |= num >> 2;
        num |= num >> 4;
        num |= num >> 8;
        num |= num >> 16;
        return Integer.bitCount(num)-1;
    }
}
 
 
class IO
{
    static byte[] buf = new byte[2048];
    static int index, total;
    static InputStream in;
    static StringBuilder sb = new StringBuilder();
 
 
    IO(InputStream is)
    {
        in = is;
    }
 
    int scan() throws Exception
    {
        if(index>=total){
            index = 0;
            total = in.read(buf);
            if(total<=0)
                return -1;
        }
        return buf[index++];
    }
    int nextInt() throws Exception
    {
        int c, val = 0;
        for(c=scan(); c<=32; c=scan());
        boolean neg = c=='-';
        if(c=='-' || c=='+')
            c = scan();
        for(; c>='0' && c<='9'; c=scan())
            val = (val<<3) + (val<<1) + (c&15);
        return neg?-val:val;
    }
}  
 
 
class Edge
{
    int u,v;    long wt;
    Edge(int a,int b,long val){u=a;v=b;wt=val;}
    int getOtherVertex(int a){return a==u? v: a==v? u: -1;}
    String getString(){return "("+u+", "+v+" -> "+wt+")";}
} 
class LCA_Sparse
{
    static final int MAXN=100_005;
    ArrayList<Integer>[] graph;
    Edge[] edges;
    int[] depth,parent,chCount;
    int n,root;
    HashMap<Long, Integer> recordLCA;
    
    LCA_Sparse(ArrayList<Integer>[] g, Edge[] e, int[] dep, int[] par, int[] ch, int node, int ro)
    {
        graph = g;  edges = e;  depth = dep;    parent = par;   chCount = ch;
        n = node;   root = ro;
        recordLCA = new HashMap<>();
        
        sparse = new int[n][];
        prepareSparse();
    }
    
    int[][] sparse;
    void prepareSparse()
    {
        int stack[] = new int[n], top = 0;
        int path[] = new int[n], end = 0;
        stack[top++] = root;
        while(top > 0)
        {
            int node = stack[--top], next;
            
            Iterator<Integer> itr = graph[node].iterator();
            while(itr.hasNext())
                if(depth[next = edges[itr.next()].getOtherVertex(node)] > depth[node])
                    stack[top++] = next;
            
            while(end > 0 && depth[path[end-1]] >= depth[node])
                --end;
            assignToSparse(path, end, node);
            path[end++] = node;
        }
    }
    void assignToSparse(int[] path, int end, int node)
    {
        if(end <= 0)return;
        sparse[node] = new int[flLog2(end) +1];
        int i, k = 0;
        for(i = 0; ; ++i)
            if(end < (1 << i)) break;
            else sparse[node][k++] = path[end - (1 << i)];
    }
    int findLCA(int u,int v)
    {
        if(u > v) { u ^= v; v ^= u; u ^=v; }
        long searchFor = u * (long) MAXN + v;
        
        if(recordLCA.containsKey(searchFor))
            return recordLCA.get(searchFor);
        
        if(depth[u] > depth[v]) u = kthParent(u, depth[u] - depth[v]);
        if(depth[u] < depth[v]) v = kthParent(v, depth[v] - depth[u]);
        
        recordLCA.put(searchFor, climbTillMerges(u, v));
        return recordLCA.get(searchFor);
    }
    int climbTillMerges(int u, int v)   // depth of 'u' & 'v' must be equal
    {
        int i;
        while(u != v)
        {
            for(i = sparse[u].length -1; i >= 0; --i)
                if(sparse[u][i] != sparse[v][i])
                    break;
            if(i < 0)
                return sparse[u][0];
            u = sparse[u][i];   v = sparse[v][i];
        }
        return u;
    }
    int kthParent(int node, int k)
    {
        while(k > 0)
        {
            int jump = Integer.highestOneBit(k);
            k ^= jump;
            node = sparse[node][flLog2(jump)];
        }
        return node;
    }
    int clLog2(int num)
    {
        --num;
        num |= num >> 1;
        num |= num >> 2;
        num |= num >> 4;
        num |= num >> 8;
        num |= num >> 16;
        return Integer.bitCount(num);
    }
    int flLog2(int num)
    {
        num |= num >> 1;
        num |= num >> 2;
        num |= num >> 4;
        num |= num >> 8;
        num |= num >> 16;
        return Integer.bitCount(num)-1;
    }
}