UVa 1357 - Cells | Sengxian's Blog

UVa 1357 - Cells

#图论 #栈模拟递归 #DFS序

Published on 2015-12-15

描述

有 $n(n\le300000)$ 个节点，他们分别可以生成 $C_{i}(C_{i}\le200)$ 个儿子。初始只有一个根节点，标号为 $0$ 。每秒当前的叶节点会按照标号大小顺序生成出儿子，直到没有节点可以生成（每个节点只会生成一次，标号大于等于 $n$ 的节点不能生成儿子）。给出 $M(M\le1000000)$ 条询问，询问节点 $a$ 是否为 $b$ 的祖先，如果是输出 Yes,否则输出 No。

样例输入

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

样例输出

Case 1:
Yes
No
No
Yes
No

Case 2:
Yes
No
Yes
No

分析

按照题目条件，我们是可以建立一棵树的，但是询问太多，而且最多有 $20000000$ 个节点，时间空间都难以承受。得想办法优化。
一个优化是不用存储树，可行的方法是定义全局时间戳 $\mathrm{timestamp}$ , 每个节点记录其开始和结束的时间 $pre[v], post[v]$ 。对于节点 $a,b$ , 如果有 $pre[a] < pre[b]$ 且 $post[a] > post[b]$ ，那么 $a$ 一定是 $b$ 的祖先，原因是 $a$ 比 $b$ 先进栈，又比 $b$ 后出栈，根据dfs的规律， $a$ 肯定是 $b$ 的祖先。
另外一个必须的优化就是用栈模拟递归，这个没什么好说的，参见代码。

代码

//  Created by Sengxian on 12/15/15.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  UVa 1357 栈模拟递归
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <stack>
using namespace std;
const int maxn = 300000 + 3, maxm = 20000000 + 3;
int n, c[maxn], sum[maxn], pre[maxm], post[maxm];

inline int ReadInt() {
    int n = 0, ch = getchar();
    while(ch < '0' || ch > '9') ch = getchar();
    do {
        n = n * 10 + ch - '0';
        ch = getchar();
    }while(ch >= '0' && ch <= '9');
    return n;
}

void dfs(int root) {
    stack<int> stk;
    stk.push(root);
    int timestamp = pre[root] = 0;
    while(!stk.empty()) {
        int u = stk.top();
        if(pre[u]) {
            post[u] = ++timestamp; //出栈了，对应dfs末尾
            stk.pop();
            continue;
        }
        pre[u] = ++timestamp; //对应dfs开始
        for(int i = sum[u]; i < sum[u] + c[u]; ++i) {
            if(i >= n) {
                //没有儿子，直接进出栈
                pre[i] = ++timestamp;
                post[i] = ++timestamp;
            }else {
                pre[i] = 0;
                stk.push(i);
            }
        }
    }    
}

int main() {    
    int caseNum = ReadInt();
    for(int k = 1; k <= caseNum; ++k) {
        if(k - 1) printf("\n");
        printf("Case %d:\n", k);
        n = ReadInt();
        //sum(i) 表示如果从节点i开始向下扩展，应该的起始标号
        for(int i = 0; i < n; ++i) c[i] = ReadInt(), sum[i] = (i == 0 ? 1 : sum[i - 1] + c[i - 1]);
        dfs(0);
        int q = ReadInt();
        for(int i = 0; i < q; ++i) {
            int a = ReadInt(), b = ReadInt();
            if(pre[a] < pre[b] && post[a] > post[b]) printf("Yes\n"); //如果a比b先进栈，又比b后出栈，则a一定是b的祖先!
            else printf("No\n");
        }
    }
    return 0;
}

UVa 610 - Street Directions 2-SAT 问题