2615 dfs(非递归).cpp

zoj 2615的代码

//zoj 2615  搜索(非递归)
/*
给出一颗最多包含三千万个点的树，需要处理一百万次查询：
给定a,b，询问a是否b的祖先。

解决思路:
查询的数量很大，必须在O(1)时间内回答每一次查询。参考LCA转化RMQ过程。
建立树，在遍历过程中记录所有第一次到达节点i的时间in[i],离开节点i的时间out[i]。然后看区间[ in[b], out[b] ]是否被 [in[a], out[a]]所真包含。若包含，说明a是b的祖先。

由于需要建二叉树，规模小的情况可以定义树节点类型，需要对树遍历时递归进行。
可是一旦规模变大，例如本题中的三千万个节点，在时间、空间限制下，上述方法不再可行。如果递归遍历，很可能导致堆栈溢出。
完全二叉树通常使用数组实现。但这里的树是多叉，并且不一定是完全的：有一些中间节点可能没有儿子。但仍然可以借鉴使用数组描述树的思想。定义如下数据结构：

*/

#include "stdio.h"

#define maksn 300100
#define maks 19000100
int begin[maksn];           //index of i's first child
int cnt[maksn];            //the number of i's children
int in[maks];             //the time of first visit node i
int out[maksn];          //the time leave node i
int p[maks];            //parent index of node i. WA when p[maksn]
int n;

void maketree()
{
 int len=1,i,k;
 scanf("%d",&n);
 for(i=0;i<n;++i)
{
  scanf("%d",&cnt[i]);
  begin[i]=len;
  len+=cnt[i];
  for(k=0;k<cnt[i];++k)
    p[begin[i] + k]=i;
}

}

void dfs()
{
  int push=1, pop=0;
  int oper=push, node=0,time=0;

  while(1)
  {
    if(oper==push)//to visit the tree rooted at node
    {
      in[node]=time++;
      if(cnt[node])//node has children
      {
        if(begin[node]<n)//first child of node within the boundary
          node=begin[node];//dfs the subtree
        else//all children of node exceeds the boundary
        {
          for(int i=0;i<cnt[node];++i)
          {
            in[begin[node]+i]=time;
            time+=2;//out[begin[node]+i] = in[begin[node]+i]+1;
          }
          oper=pop;//already visited the leaves
        }
      }
      else//node is leave
        oper=pop;
    }
    else//have visited the tree rooted at node
    {
      out[node]=time++;//leave node
      if(node==0)
        break;
      int parent=p[node];
      if(node<begin[parent]+cnt[parent]-1)
      { //node has siblings.
        ++node;//move to sibling
        oper=push;
        if(node>=n)
        {//boundary case:
          //node is within boundary while siblings not.
          //i.e, the boundary splits the children of parent of node
          //the siblings must be leaves
          for(;node<begin[parent]+cnt[parent];++node,time+=2)
            in[node]=time;
          node=parent;//visited all children.
          oper=pop;//backtrack to parent
        }
      }
      else//node has no siblings
        node=parent;
    }
  }
}

int main()
{
 int t,i,j,m,kase=1,a,b;
 //freopen("2615.txt","r",stdin);
 scanf("%d",&t);
 while(t--)
 {
  maketree();
  dfs();
  
  scanf("%d",&m);
  printf("Case %d:\n",kase++);
  
  for(i=0;i<m;i++)
  {
   scanf("%d %d",&a,&b);

   if(a>=n||a==b)
    {
     puts("No");
     continue;
    }
   int leave=(b<n? out[b]:in[b]+1);
   if(in[b]>in[a] && leave<out[a])
     puts("Yes");
   else
     puts("No");

  }
   if(t) printf("\n");
 }
 return 0;
}