UVA 1357 Cells ( 水題時間戳記 )

UVa Online Judge
題目要求多筆詢問回答 a是否為 b的祖先。可以用時間戳記做樹壓平，只要 b所代表的區間[ in[ b ], out[ b ] ) 包含於 a的區間就說是。這題比較特別的是葉節點可以到很大，如果真的一一拜訪下去會 RE，所以必須不拜訪直接處理。除錯了好久才知道原來 LRJ說的「注意堆疊溢出」是這個意思，起初寫了遞迴開了我寫在第一行的修改編譯參數沒過，又去寫一個堆疊版本依然沒過，這時候我才理解是這個題目的特殊性＝＝。這題是真水題，要是正式的時候搞這樣的烏龍就掰了啊。。

#pragma comment(linker , "/STACK:102400000,102400000")
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 5;
const int MAXC = 100 + 2;
const int MAXM = 1e6 + 6;
const int MAXTOT = 2e7 + 7;

int n, m;
int c[MAXN], fson[MAXN]; // id of first son

int dfs_clock;
int in[MAXTOT], out[MAXTOT];

void dfs(int u){
    in[ u ] = ++dfs_clock;
    for(int v = fson[u]; v < fson[u] + c[u]; ++v){
        if( v < n ) dfs( v );
        else in[ v ] = ++dfs_clock, out[ v ] = dfs_clock;
    }
    out[ u ] = dfs_clock;
}
/*
void dfs(int root){
    stack<int> stk; stk.push( root );
    while( !stk.empty() ){
        int u = stk.top(); stk.pop();
        if( !in[ u ] ){
            in[ u ] = ++dfs_clock;
            stk.push( u );
            for(int v = fson[ u ]; v < fson[ u ] + c[ u ]; ++v){
                if( v < n ) stk.push( v );
                else in[ v ] = ++dfs_clock, out[ v ] = dfs_clock;
            }
        } else
            out[ u ] = dfs_clock;
    }
}
*/
void preprocess(){
    int cnt = 1;
    for(int i = 0; i < n; ++i){
        fson[i] = cnt;
        cnt += c[i];
    }
    dfs_clock = 0;
    memset( in, 0, sizeof(in) );
    memset( out, 0, sizeof(out) );
    dfs( 0 );
}

int main(){
    int T; scanf("%d", &T);
    for(int kase = 1; kase <= T; ++kase){
        if( kase > 1 ) puts("");
        printf("Case %d:\n", kase);
        scanf("%d", &n);
        for(int i = 0; i < n; ++i)
            scanf("%d", &c[i]);
        preprocess();
        scanf("%d", &m);
        while( m-- ){
            int a, b; scanf("%d%d", &a, &b);
            if( in[ a ] < in[ b ] && out[ b ] <= out[ a ] ) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}