Uva(1357)(Cells)

链接：https://vjudge.net/problem/UVA-1357
思路：太妙了太妙了，再次感叹自己智商不够了。。利用dfs的特性，在dfs的时候给每个点标上开始查找时间和结束查找时间，则如果满足祖先和子孙关系的话两个的时间应该是包含关系，其他的都是不相交关系。由于数量级较大不能直接dfs，用栈模拟即可！！！
代码：

#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <stack>
#include <algorithm>
 
using namespace std;
const int maxn = 3 * 1e5 + 5;
const int maxm = 2 * 1e7 + 5;
 
int N, M, S[maxn], C[maxn], pre[maxm], post[maxm];
 
void dfs(int root) {
    stack<int> sta;
    sta.push(root);
    int dfslock = pre[root] = 0;
 
    while (!sta.empty()) {
        int x = sta.top();
        if (pre[x]) {
            post[x] = ++dfslock;
            sta.pop();
            continue;
        }
 
        pre[x] = ++dfslock;
        for (int i = S[x]; i < S[x] + C[x]; i++) {
            if (i < N) {
                pre[i] = 0;
                sta.push(i);
            } else {
                pre[i] = ++dfslock;
                post[i] = ++ dfslock;
            }
        }
    }
}
 
int main () {
    int cas, u, v;
    scanf("%d", &cas);
    for (int kcas = 1; kcas <= cas; kcas++) {
        scanf("%d", &N);
        S[0] = 1;
        for (int i = 0; i < N; i++) {
            scanf("%d", &C[i]);
            if (i) S[i] = S[i-1] + C[i-1];
        }
 
        dfs(0);
 
        scanf("%d", &M);
        printf("Case %d:\n", kcas);
        for (int i = 0; i < M; i++) {
            scanf("%d%d", &u, &v);
            printf("%s\n", pre[u] < pre[v] && post[u] > post[v] ? "Yes" : "No");
        }
        if (kcas < cas) printf("\n");
    }
    return 0;
}