HDU3896 - Greatest TC

HDU3896 - Click Here

  

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.

  

Solutions

  这题是好题啊。。。刚开始还以为直接判断割顶和桥就好了,结果被KsCla无情的驳回了。。。

  题目要求,删除某边或某点后是否依旧能够到达,这与联通分量极为相似。因此,我们可以利用联通分量的做法,遍历一次图,得到一棵DFS树。每个节点记录dfn,low,dep值,分别对应该点dfs序,该点能到达的最小dfs序以及该点所处深度

  

  对于删边询问,有几种情况。

  此处不妨假设$dep[c]<dep[d]$,即d为c的儿子。

  定义边集$E$为参与DFS树构建的边的集合。

  1.若$(c,d) \notin E$,即$|dep[c]-dep[d]|>1$。那么显然删除这条边后,对这棵树中任意节点均无影响。(yes)

  2.若$(c,d) \in E$且a,b同d的子树内。显然a,b之间一定存在着a->d->b这样的路径,因此删边后不会有影响。(yes)

  3.若$(c,d) \in E$且a,b同不在d的子树内。显然a,b之间的路径一定不会经过(c,d),因此删边后不会产生影响。(yes)

  4.若$(c,d) \in E$且a,b有一个在d的子树内(此处不妨假设为a)。那么若要使得删边后不会产生影响,必定满足下列中的其中一种情况。

  State1.这种情况下,a到达某个儿子节点,再从某条$(u,v) \notin E$的边到达b。此时,满足$low[a]<dep[d]$,即a能够到达的节点是d的祖先。因此这种情况下,删边后不会产生影响。(yes)

  State2.这种情况下,a到达某个祖先节点f(同时为d的儿子节点),再从某条$(u,v) \notin E$的边到达b。此时,满足$low[f]<dep[d]$,即f能够到达的节点是d的祖先。因此这种情况下,删边后不会产生影响。(yes)

  由于我们不清楚,$(u,v) \notin E$的边是与a的儿子相连还是与a的祖先相连。为了能够一次判断出来,我们选择能够囊括所有满足要求的节点的信息进行判断,即a->d路径上的倒数第二个节点,假设为p。若$low[p]<dep[d]$,删边不产生影响(yes),否则删边产生影响(no)。

  

  理清了删边的情况后,删点就十分相似了。同样分为几种情况考虑。

  1.若a,b同不在c的子树内。显然a,b之间的路径一定不会经过c,因此删点后不会产生影响。(yes)

  2.若a,b有一个在c的子树内(此处不妨假设为a)。利用与删边时相同的技巧,选取a->c路径上的倒数第二个节点,假设为p。若$low[p]<dep[c]$,删点不产生影响(yes),否则删点产生影响(no)。

  3.若a,b同c的子树内。

  State1.若$LCA(a,b) \neq c$。显然$LCA(a,b)$也必定在c的子树内,因此存在a->$LCA(a,b)$->b这样的路径。删点后不会产生影响。(yes)

  State2.若$LCA(a,b) = c$。若a要能够到达b,必须a能够到达c的祖先b也能够到达c的祖先。利用删边时使用的技巧,选取a->c路径上的倒数第二个节点,假设为p;选取b->c路径上的倒数第二个节点,假设为q。若$low[p]<dfn[c] \& low[q]<dfn[c]$,删点不产生影响(yes),否则删点产生影响(no)。

  

  P.S. 判断a是否在b的子树内的方法。

  如果$LCA(a,b)=b$,则a在b的子树内;否则不在子树内。

  或者可以记录每个节点开始dfs和结束dfs的时间戳,判断是否为包含关系,即可得知是否在子树内。

  

CODE

CODE - Click Here

本站总访问量次 | 本站访客数人次

Powered by Hexo | Designed by iTimeTraveler | Refined by CSHwang