UVALive3486 / ZOJ2615 Cells 栈模拟DFS

THE 30th ACM/ICPC ASIA REGIONAL 2005 HANGZHOU SITE

Onsite Contest Session

Problem C: Cells

Scientists are conducting research on the behavior of a newly discovered Agamic Cellular Microbe. This special kind of microbe is capable of massively reproducing by itself in a short time. The lifetime of an ACM consists of three phases:

科学家们正在研究一种新发现的无性细胞微生物的行为。这种特殊的微生物能在短时间内大量繁殖。ACM的生命周期包括三个阶段:

1. The infancy phase, which starts from its birth and lasts for approximately several seconds; 2. The multiplication phase, in which one ACM can procreate up to 100 offspring in only several milliseconds; 3. The mature phase, in which it remains inactive for the rest of its life.

1、婴儿期，从婴儿出生开始持续大约几秒钟;

2。成长阶段，一个ACM可以在几毫秒内产生100个后代;

3.成熟阶段，在此阶段中，它将终生处于不活跃状态。

At the beginning of the experiment, a newborn, single cell of ACM, is put into a suitable circumstance for its production. This cell, numbered as 0, starts to multiply and its descendants are numbered, starting from 1, according to their positions in the family hierarchy. During the experiment special equipment is used to record the numbers of the offspring generated by each of the ACM's. The experiment is stopped after a certain time period.

The family tree of ACM's in the first case of sample input

Your task is to help the scientists to determine whether one ACM is an ancestor of another.

在实验开始时，将新生的ACM单细胞放入合适的环境中进行生产。这个细胞编号为0，开始繁殖，根据其在家族等级中的位置从1开始编号。在实验过程中，使用特殊设备记录ACM每一个子代产生的子代数，实验在一段时间后停止。你的任务是帮助科学家确定一个ACM是否是另一个ACM的祖先。

Input Description

Standard input will contain multiple test cases. The first line of the input is a single integer T (1 <= T <= 10) which is the number of test cases. T test cases follow, each preceded by a single blank line.

Each test case starts with a single integer N (1 <= N <= 300,000) which is the number of ACM's that have their descendants recorded. The following N integers (not necessarily on a same line), Ci (0 <= i < N, 0 <= Ci <= 100), give the number of offspring of the i-th ACM. The next line contains an integer M (1 <= M <= 1,000,000) which is the number of queries. M lines follow, each contains two integers a and b, querying whether the a-th ACM is an ancestor of the b-th ACM.

The total number of ACM's may be greater than N, but would never exceed 20,000,000.

Output Description

Results should be directed to standard output. Start each case with "Case #:" on a single line, where # is the case number starting from 1. Two consecutive cases should be separated by a single blank line. No blank line should be produced after the last test case.

For each query, print either "Yes" or "No" on a single line, which is the answer to the query.

Sample Input

2 

6 
3 2 1 1 0 2 
5
0 1 
2 4 
3 5 
1 8 
6 9 

5 
2 0 3 0 1 
4
2 6 
1 6 
2 3 
3 5

Sample Output

Case 1: 
Yes 
No 
No 
Yes 
No 
Case 2: 
Yes 
No 
Yes 
No

题意：

给一棵有根树，有N个节点，接下来N个数表示第i个节点的子节点数量，子节点从1开始编号；然后是M次询问，若a是b的祖先，输出Yes，否在输出No

分析：

如果数据量很小，直接暴力DFS即可。

但是考虑最坏的情况，30w层，2000w个点，询问100w次，貌似连dfs一遍都会TLE（超时）。

1、2000w个点不一定都要保存下来，事实上，虽然题目给了256M的空间，只要开了两个这么大的数组，MLE是跑不了的，所以只保存30w个父节点。

2、如果这30w个父节点构成一条链，dfs的栈肯定爆。所以需要用栈模拟dfs。可以用STL里的stack，当然手写栈会更快。

注意：1、时间戳的使用。

　　 2、本题中顺序对节点标号，使得所有>=n的节点都是叶子节点，同时能够二分也是因为它是有序的。

源代码：

#include
#include
#include
#include
using namespace std;
const int maxn = 3e5 + 10, maxm = 2e7 + 10;
int n, m;
int num[maxn];//num[i]表示i号节点的儿子个数
int child[maxn];//child[i]表示i号节点第一个儿子的编号
int now[maxn];//用来记录当前判断的子节点
int my_stack[maxm], top_stack;
int in[maxm], out[maxm]; //用来记录进栈出栈次序
//使用栈模拟DFS
//子节点的进栈一定晚于父节点，出栈一定早于父节点
void my_dfs()
{
    for (int i = 0; i < n; i++)
        now[i] = 0;
    int c = 0;
    top_stack = 0;
    my_stack[0] = 0;
    in[0] = c++;
    while (true) {
        int fron = my_stack[top_stack];
        //大于等于n一定没有子节点，直接出栈
        if (fron >= n) {
            out[fron] = c++;
            top_stack--;
        }
        fron = my_stack[top_stack];
        int i = child[fron] + now[fron];
        if (now[fron] == num[fron] && top_stack == 0) //判断是否遍历完
        {
            out[fron] = c;
            return ;
        }
        //判断栈顶元素的子节点是否遍历完
        else if (now[fron] == num[fron]) {
            out[fron] = c++;
            top_stack--;
        }
        else { //入栈
            now[fron]++;
            my_stack[++top_stack] = i;
            in[i] = c++;
        }
    }
}
//若a是b的父节点，返回true
bool query(int a, int b)
{
    if (a >= b || a >= n || in[a] > in[b] || out[a] < out[b])
        return false;
    return true;
}
int main()
{
    int T, ca = 1;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        int top = 1; //子节点从1开始编号
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &num[i]);
            child[i] = top;
            top += num[i]; //更新第一个子节点编号
        }
        my_dfs();//预处理出栈、入栈次序
        if (ca != 1)   printf("\n");
        printf("Case %d:\n", ca++);
        scanf("%d", &m);
        while (m--) {
            int a, b;
            scanf("%d%d", &a, &b);
            if (query(a, b))
                printf("Yes\n");
            else
                printf("No\n");
        }
    }
    return 0;
}