学LCA的时候根本没意识到LCA可以有这么多玩法。
这玩意据说是个高级数据结构(支配树)的弱化版,蒟蒻没学过呀。所以出题人提出一个概念叫灾难树。
我理解的灾难树的意思实际上是属于DAG的一个子图(我不知道怎么描述,就叫子图吧!)。灾难树关于DAG有这样一个性质。就是说在DAG上删掉某一点后,如果存在一个点的入度变为0.那么这个点就删去,以此类推,而被删去的点是这个所有*删除的点的父亲。
上面实际上就是把题面描述了一遍QAQ。
如何根据原DAG构建灾难树呢?
首先把DAG拓扑排个序。然后逆序遍历,对于拓扑序上的每一个点。找到他所有子节点在新图上的LCA(如果不存在或者LCA就是该节点就设为0)。然后就在新图上由LCA向这个点连边。最后形成的新图就是灾难树。
其实如果偏感性的理解的话,就是如果一个点所有出边所连接的点,或者通俗点说,就是所有食物都没了,那么这个点是一定要随之被删掉的。也就是说LCA的被删去必定会导致当前节点的被删去。
//BZOJ 2815 //by Cydiater //2016.10.21 #include <iostream> #include <cstring> #include <string> #include <algorithm> #include <queue> #include <map> #include <ctime> #include <cmath> #include <iomanip> #include <cstdlib> #include <cstdio> using namespace std; #define ll long long #define up(i,j,n) for(int i=j;i<=n;i++) #define down(i,j,n) for(int i=j;i>=n;i--) const int MAXN=1e6+5; const int oo=0x3f3f3f3f; inline int read(){ char ch=getchar();int x=0,f=1; while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int N,LINK[MAXN],len=0,indu[MAXN],head,tail,q[MAXN],Link[MAXN],LEN=0,fa[MAXN][21],dep[MAXN],siz[MAXN]; struct edge{ int y,next; }e[MAXN],E[MAXN]; namespace solution{ inline void insert(int x,int y){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;} inline void Insert(int x,int y){E[++LEN].next=Link[x];Link[x]=LEN;E[LEN].y=y;} void init(){ N=read(); memset(indu,0,sizeof(indu)); up(i,1,N){ int y=read(); while(y){insert(i,y);indu[y]++;y=read();} } } int LCA(int x,int y){ if(x==-1)return y; if(dep[x]<dep[y])swap(x,y); down(i,20,0)if(dep[x]-(1<<i)>=dep[y])x=fa[x][i]; if(x==y) return x; down(i,20,0)if(fa[x][i]!=fa[y][i]&&fa[x][i]!=0){ x=fa[x][i]; y=fa[y][i]; } return fa[x][0]; } void get_ancestor(int node){ up(i,1,20)if(fa[node][i-1]!=0)fa[node][i]=fa[fa[node][i-1]][i-1]; } void dfs(int node){ siz[node]=1; for(int i=Link[node];i;i=E[i].next){ dfs(E[i].y); siz[node]+=siz[E[i].y]; } } void slove(){ head=1;tail=0;up(i,1,N)if(!indu[i])q[++tail]=i; for(;head<=tail;head++){ int node=q[head]; for(int i=LINK[node];i;i=e[i].next) if(--indu[e[i].y]==0)q[++tail]=e[i].y; } down(h,tail,1){ int node=q[h],lca=-1; for(int i=LINK[node];i;i=e[i].next)lca=LCA(lca,e[i].y); if(lca==node||lca==-1)lca=0; Insert(lca,node);fa[node][0]=lca;dep[node]=dep[lca]+1; get_ancestor(node); } memset(siz,0,sizeof(siz)); dfs(0); } void output(){ up(i,1,N)printf("%d\n",siz[i]-1); } } int main(){ //freopen("input.in","r",stdin); using namespace solution; init(); slove(); output(); return 0; }