URAL 1329. Galactic History

1. 题目

http://acm.timus.ru/problem.aspx?space=1&num=1329

1329. Galactic History

Time limit: 1.0 second
Memory limit: 64 MB
It is very hard for one person to learn all galactic history. But, on the other hand, every diplomat who wants to hold a more important post in a galactic empire must know the subject well. For example, letting a spoon fall among high-rankers of the star system Arcturus means offending them awfully. (Didn’t you hear that the last conflict between systems Arcturus and Alpha flamed up because of the only shattered glass?)
Fortunately, the solution was found in the Galactic Academy. For diplomats of the lower rank it is enough to learn just a single branch of history – the one that concerns only the cluster of star systems, in which he is going to work. (Diplomats of the lower rank negotiate only with planets that are located in one star cluster. How come we didn’t guess this earlier?)
Taking this very important observation into consideration, it was decided to replace a single intergalactic course with several separate courses, each covering only the part of history that refers to only one star cluster. Of course, it is necessary to learn history in chronological order, beginning from the origin of humanity. That’s why the history of the Earth needs to be included in all collections of separate histories. Then things become complicated: for example, emigrants from Centaurus system colonized the star system of Herdsman, so the textbook on the history of Herdsman system has to contain the early history of Centaurus system. In order to decide, in which textbooks which phases of history should be included, historians of Galactic Academy divided general intergalactic history into many small milestones. Then all milestones were combined into one big tree (omnipresent biologists helped historians in this work, as they had always been using these trees). The milestone referring to early history of the Earth (before the space colonization) was declared the root. Milestones referring to history of star systems close to solar system appear to be its sons (because these systems were colonized by emigrants from Earth) and so on. That’s all! To determine milestones that have to be included in a particular textbook it is only required to determine quickly, whether the milestone A is located in a subtree with the root in milestone B.

Input

In the first line there is a number N (N ≤ 40000), which defines the total number of milestones. In the next N lines there are descriptions of each milestone.
Each milestone is defined by two numbers: ID – an unique numerical identifier of a milestone and ParentID – identifier of the milestone which is its father in a tree. ParentID for the root equals to -1.
(N+2)th line contains number L (L ≤ 40000) – amount of queries. The next L lines contain descriptions of queries: on each line there are two different numbers A and B. All identifiers lie between 0 and 40000.

Output

For each query it is necessary to write in separate line:

  • 1, if milestone A is a root of subtree which contains milesone B.
  • 2, if milestone B is a root of subtree which contains milesone A.
  • 0, if no one of the first two conditions is true.

Sample

input output
Problem Author: Evgeny Krokhalev
Problem Source: The 10th Collegiate Programming Contest of the High School Pupils of the Sverdlovsk Region (October 16, 2004)

2. 思路

银河系历史被划分为由里程碑构成的树状结构,给出若干里程碑及其父子关系,并给出若干查询条目,求每个查询条目中两个里程碑间的关系(一个是另一个的根,或者没有关系)。

由输入数据给出的各里程碑关系,构建一个树,没有难度。此题的陷阱在于,查询条目最多有40000条,如果一条一条查,会超时;需要在对树的一次遍历中,把所有条目查询完。

在下面的代码中,使用 aList[i] 和 bList[i] 分别存储第i个查询中包含的两个里程碑A和B,用 statusList[i] 表示第i个查询条目的查询状态,初始化为 STATUS_NOT_FOUND 。同时,以邻接表的形式保存每个查询,每个查询对应一个结构体 Query , Query 有两个字段, queryId 和 next : queryId 为查询条目的id, statusList[queryId] 、 aList[queryId] 和 bList[queryId] 分别对应了 queryId 查询条目的查询状态、A和B; next 指向下个 Query ,使得对于每个里程碑m, query[m] 成为一个链表,存储了所有包含有m的查询。

对树进行一次先序遍历,对于每个节点n,通过 query[n] 可以得到所有包含有n的查询,对于每个包含有n查询,根据其 queryId ,由 statusList[queryId] 得到该查询的状态,进行相应处理:

  • 如果 statusList[queryId] 为 STATUS_NOT_FOUND ,则若当前节点 n == aList[queryId] ,则令 statusList[queryId] = STATUS_FOUND_A ;若当前节点 n == bList[queryId] ,则令 statusList[queryId] = STATUS_FOUND_B ;
  • 如果 statusList[queryId]STATUS_FOUND_A ,则若当前节点 n == bList[queryId] ,查询完成,令 statusList[queryId] = STATUS_A_IS_ROOT_OF_B ;
  • 如果 statusList[queryId]STATUS_FOUND_B ,则若当前节点 n == aList[queryId] ,查询完成,令 statusList[queryId] = STATUS_B_IS_ROOT_OF_A ;

每遍历完一棵子树,检查一遍 statusList[] :如果其中有 STATUS_FOUND_A ,说明在这个子树中,只找到了这个查询中的里程碑A,对于查询中的另一个里程碑B,可能在别的子树或根本不存在,查询失败,将其查询状态置为 STATUS_NONE ;同理对于 STATUS_FOUND_B ,也表明查询失败,置为 STATUS_NONE 。

3. 代码