Trees and Queries

Problem

An arbitrary rooted tree whose edges have no weight and no direction is given. Answer the query below.

Print the number of vertices in the subtree rooted at vertex $U$ .

If you have trouble solving this problem, read the explanation in the hint at the bottom.

Input

The first line contains the number of vertices $N$ in the tree, the number $R$ of the root, and the number of queries $Q$ . ( $2 \le N \le 10^5$ , $1 \le R \le N$ , $1 \le Q \le 10^5$ )

Each of the next $N-1$ lines contains an edge of the tree in the form $U$ $V$ . ( $1 \le U, V \le N$ , $U \ne V$ )

This means the edge whose two endpoints are $U$ and $V$ belongs to the tree.

Each of the next $Q$ lines contains one $U$ as described in the problem. ( $1 \le U \le N$ )

The tree given in the input is guaranteed to be a valid tree.

Output

Print the answer to each query as a single integer, one per line, over $Q$ lines.

Hint

A graph is a set made of vertices and of edges that join two vertices.

The picture above is a graph made of 9 vertices (the circles) and 10 edges (the solid lines). The number written inside each circle is the index assigned to that vertex for convenience.

The red edges are colored in advance for a later part of the explanation. For now, treat them as identical to the other black edges.

An edge always joins two vertices. From here on, a vertex is written by its number (vertex 1, vertex 2) and an edge by the numbers of its two endpoints (1-3, 3-2).

The edges of a graph may have weights. If nothing is said, treat every edge as having weight 1. If weights exist and, for example, edge 1-3 has weight 3, then going from vertex 1 to vertex 3 means passing an edge of length 3. The graph above is an example where every edge has length 1.

The edges of a graph may have directions. For example, the edge 1-3 between vertex 1 and vertex 3 can be directed from 1 to 3, or from 3 to 1. A graph that has directed edges is called a directed graph, and a graph made only of undirected edges, like the picture above, is called an undirected graph. The direction of an edge changes the result of a traversal. In the graph above, the path from vertex 1 to vertex 4 that uses the fewest edges visits 1, 3, 4 and uses 2 edges. We say that the shortest path between vertex 1 and vertex 4 is 2. If the edge between vertex 3 and vertex 4 were directed from 4 to 3, then the shortest path from vertex 1 to vertex 4 would visit 1, 3, 6, 5, 4 and pass 4 edges, so the shortest path would be 4.

A graph has cycles. In an undirected graph a cycle is a path that starts at some vertex and returns to the starting point without visiting any vertex other than the starting point, and without using any edge, more than once. For example, the picture above has the cycle 3-6-5-4-3 and the cycle 6-7-9. The path 1-3-1 uses the edge 1-3 twice, so it is not a cycle, and 1-3-6-5-4-3 never returns to the starting point, so it is not a cycle either.

If a graph has no cycle at all, that graph is called a tree. The name comes from the graph looking like a tree that grew out of one vertex. For example, removing the two red edges from the picture above turns the graph into a tree. The tree made by removing the two red edges from the graph above looks like this.

A graph normally ignores the position of a vertex and the shape of an edge and considers only connectivity, so as long as the set of edges does not change you may redraw the graph however you like. Think of grabbing vertex 5 in the tree above and lifting it upward. If gravity pulls downward and you lift vertex 5 up, the shape of the tree changes like this.

As long as the set of edges is unchanged, you may redraw the graph however you want. For example, mirroring the tree above left to right still gives the same tree.

A tree may or may not have a root, but for convenience you may pick any vertex as the root. Look at the tree above again, assuming vertex 5 is the root.

Because a tree can always be redrawn around its root, you cannot decide which vertex is above another unless the root is fixed. Once the root is fixed, you can define a parent and child relation between vertices. In the tree above the parent of vertex 4 is vertex 5, and vertex 3 is a child of vertex 4. Vertex 5 has no parent and has vertices 4 and 6 as its two children.

A tree has several important properties. Two of them are below.

For any two vertices $U$ and $V$ , the shortest path from $U$ to $V$ is unique.
Take any vertex and cut its link to its parent. The subgraph made of that vertex, its children, the children of those children, and so on, is a tree.

Both are intuitive and obvious, so the proofs are omitted. In the second property, the tree made from the cut subgraph is called a subtree.

Suppose a problem about a tree is set. It is nice when the input is given as a root and its children like the drawing above, but the input may instead be a plain tree with no root (the second picture). For example, if only the number of vertices and the list of edges is given, how do you build the tree?

Suppose the number of vertices and the list of edges for the tree above are given as follows.

The 9 on the first line is the number of vertices, and the remaining 8 pairs of integers are the endpoint numbers of the edges. It is well known that the number of edges in a tree is always the number of vertices minus 1, and the proof is not hard, so it is omitted.

To build a tree from data like this, it is easier to pick one root first. Let vertex 5 be the root.

A tree has a parent and child relation, so storing, for each vertex, which vertex is its parent and what its list of children is turns out to be useful. Implement it as follows.

def makeTree(currentNode, parent):
    for Node in connect[currentNode]:
        if Node != parent:
            add Node to currentNode's child
            set Node's parent to currentNode
            makeTree(Node, currentNode)

currentNode is the vertex being visited, and parent is the parent vertex of that vertex.

In a tree, a vertex has one parent or none. So every vertex joined to a given vertex, with at most one exception, is a child of that vertex. The function therefore carries the parent vertex along, takes every vertex joined to itself that is not the parent as its own child, sets the parent of each such vertex to itself, and then recursively asks the child vertices to build their part of the tree.

After defining it this way, calling makeTree(5, -1) once in the main function builds the tree rooted at vertex 5. The -1 means there is no parent.

Now think about a plain tree where a root is given and many queries follow. For the tree rooted at vertex 5, suppose the query how many vertices are in the subtree rooted at vertex $U$ is asked many times. As said above, the subtree rooted at $U$ is the tree made by cutting the link between vertex $U$ and its parent and taking $U$ , its children, the children of those children, and so on. For example, when vertex 5 is the root, the subtree rooted at vertex 4 has 4 vertices, and the subtree rooted at vertex 8 has 1 vertex.

Cutting the link and counting the vertices again for every query is possible, but if the tree has many vertices and there are many queries, the program will probably not finish within the time limit. It would be good to have a way to compute in advance, and quickly, the number of vertices in the subtree rooted at each vertex.

To do that, look at how the tree building code runs. It starts at the root and asks each child vertex once to build its part of the tree. What this tells you is that once makeTree returns for a child vertex, the subtree rooted at that child vertex is finished. Using the same idea, write a function that computes, for every vertex, the number of vertices in the subtree rooted at that vertex.

def countSubtreeNodes(currentNode):
    size[currentNode] = 1
    for Node in currentNode's child:
        countSubtreeNodes(Node)
        size[currentNode] += size[Node]

The size starts at 1 rather than 0 because a vertex belongs to the subtree rooted at itself. The function computes the subtree vertex counts of all the child vertices, then adds them up to get the number of vertices in the subtree rooted at itself. Calling makeTree(5, -1) and then countSubtreeNodes(5) once each in the main function precomputes, for every vertex of the tree rooted at 5, the number of vertices in the subtree rooted at that vertex. With that, every query $U$ only needs size[U] printed, so even data with 100,000 vertices and 100,000 queries is handled fast enough.