Description
This is a partial judge problem. o_O
In this problem, you're given an undirected tree with N vertices. Then, there're Q queries which are independent. For each query, given two vertices a, b, please remove edge (a, b) from the tree and output the maximum index in the two trees separated by edge (a, b) respectively.
You're asked to implement graph structure by adjacency list.
struct Node { int id; struct Node *next; }; struct Graph { int vertices_num; struct Node **adjLists; };
First of all, you have two struct. vertices_num in Graph represents number of vertices in the tree, and the adjLists represents all the collection of edges in this graph, adjLists[i] represents the list that store the neighbors of i-th vertex. Node is used as a node in the adjLists.
Next, you have to implement the following four functions.
struct Graph* createGraph(int);
You have to create a Graph with the parameter as the number of vertices.
void addEdge(struct Graph*, int, int);
Add an edge to the graph. Since it's an undirected tree, so you have to add v in the adjLists[u] and add u in the adjLists[v].
int findMax(struct Graph*, int, int);
The function is aim to traverse the enitre tree recursively and return the maximum index in the tree. In the general graph, you have to store whether the vertex has been traveled before in order to avoid repeated traversal. But in this problem, the graph is a tree, which means you can simply avoid traversing to the previous node that enter to current node to prevent from repeated traversal.
For instance,
If we cut off edge (0, 1), we can start calling findMax in vertex 0 and set its previous traveled vertex as 1, then it won't travel to vertex 1. Same logic can apply to vertex 1, we can set its previous traveled vertex as 0, then it won't travel to vertex 0.
int findMax(struct Graph* g, int now, int pre) { ... for (struct Node* it = g->adjLists[now]; it; it = it->next) { if (it->id == pre) continue; ... } ... }
The above section are the example code that we expect you to do.
void freeGraph(struct Graph*);
Free the space of the entire graph.
If you think the above description is not clear, you should trace the sorce code for detailed.
You're highly recommended to create an additional file function.c and compile it with the main source code instead of putting everything into one file.
Input
The input contains T testcases.
The first line of each testcase contains a single integer N, (N <= 200000) representing the number of vertices. Vertices is 0-based indexing. The following N - 1 lines representing the edge in the tree. Each line contains 2 integer u, v, representing an edge connect vertex u and vertex v. Next line of input contains single integer Q, representing the number of qureies. The following Q lines each contains 2 integer a, b, representing the removed edge. Guarantee that the edge exists in the tree, but the order of a, b may vary, that is, a b and b a refer to the same edge.
Guarantee that Ｎ＊Ｔ＊Ｑ <= 2000000.
Output
For each query, please output the maximum index in the two trees separated by edge (a, b) respectively.