Greatest TC

Time Limit: 12000/4000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 509 Accepted Submission(s): 148

Problem Description TC (Tian Chao) is magical place, as you all know...
The railways and the rail-stations in TC are fragile and always meet with different kinds of problems. In order to reach the destination safely on time, you are asked to develop a system which has two types of main functions as below.
1: A B C D, reporting whether we can get from station A to station B without passing the railway that connects station C and station D.
2: A B C, reporting whether we can get from station A to station B without passing station C.
Please notice that the railways are UNDIRECTED.
Input For each test case, the first line will contain two integers N (2<=N<=100000) and M (1<=M<=500000), namely the number of stations and railways in TC. Then each of the next M lines will have two integers, describing the two stations that a certain railway is connecting. After this, there comes a line containing a single integer Q (Q<=300000), which means the number of queries to make on the system. The next Q lines will be queries. Each query begins with a integer, indicating the type of query, followed by 4 (the first type) or 3 (the second type) integers describing the details of the query as what mentioned above.
The stations are always labeled from 1 to N.
Output For each test case, print "yes" or "no" in separated lines for the queries.
Sample Input

Sample Output

yes
yes
yes
no
yes

题意:给定一个图，有两种询问，第一种，从a-b是否经过c-d的路径，从a-b是否经过c点。

根据tarjan可以得到一个dfs序，记录第一次经过这个点的时间戳，已经离开这个点的时间戳，每一个点只访问一次，
记录预处理倍增数组。
对于查询1，假设c在d的下边，讨论a,b与c的关系，假如a，b都是c的子树上的点，或者都不是，那么显然存在，只需要讨论
一个在c的子树上，一个不在的情况，假如a在c的子树上假如a的low值小于等于c的dfn，则显然可以，否则不能。
对于查询2，假如a，b都不在c的子树上，则显然可以。
假如都在c的子树上，那么找a，b在c下方的点pp，qq，假如pp==qq，则显然不需要经过c，如果pp，qq都可以查找到c前面的点，那么a，b可以经过pp，qq
到达c的前面，显然可以绕过c相遇。
剩下的就是a，b中有一个在c的子树上，假如a，那么找a在c下方的那个点pp，假如pp存在，那么看pp是否可以返祖到c的前面，假如可以，那么肯定可以
找到不经过c的路径。
好恶心的题目，折腾了一天，在别人的指导下终于ac了，wa30次，坑爹。
代码：

/* ***********************************************
Author :_rabbit
Created Time :2014/5/2 13:43:24
File Name :12.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
                using namespace std; #define INF 0x3f3f3f3f #define eps 1e-8 #define pi acos(-1.0) typedef long long ll; const int maxn=101000; const int maxm=1001000; int head[maxn],tol; int low[maxn],dfn[maxn],indexx; int fa[maxn][20],dep[maxn],out[maxn]; int vis[maxm]; struct Edge{ int next,to; }edge[maxm]; void addedge(int u,int v){ edge[tol].to=v; edge[tol].next=head[u]; head[u]=tol++; } void tarjan(int u,int deep){ low[u]=dfn[u]=++indexx; dep[u]=deep; for(int i=head[u];i!=-1;i=edge[i].next){ if(vis[i])continue; vis[i]=vis[i^1]=1; int v=edge[i].to; if(!dfn[v]){ tarjan(v,deep+1); fa[v][0]=u; low[u]=min(low[u],low[v]); } else low[u]=min(low[u],dfn[v]); } out[u]=indexx; } bool judge1(int a,int b,int c,int d){ if(dep[c]
                
                 =dfn[c]&&out[a]<=out[c])ina=1; if(dfn[b]>=dfn[c]&&out[b]<=out[c])inb=1; if((ina&&inb)||(!ina&&!inb))return 1; else{ if(low[c]<=dfn[d])return 1; return 0; } } int move(int x,int step){ if(step<0)return -1; for(int i=19;i>=0;i--) if((1<
                 
                  =dfn[c]&&out[a]<=out[c])ina=1; if(dfn[b]>=dfn[c]&&out[b]<=out[c])inb=1; int flag=0; if(!ina&&!inb)flag=1; else if(ina&&!inb){ int pp=move(a,dep[a]-dep[c]-1); if(pp!=-1&&low[pp]

HDU 3896 dfs树倍增

Greatest TC