阿米巴是小強的好朋友。

阿米巴和小強在草原上捉螞蚱。小強突然想，果螞蚱被他們捉滅絕了，那么吃螞蚱的小鳥就會餓死，而捕食小鳥的猛禽也會跟著滅絕，從而引發一系列的生態災難。

學過生物的阿米巴告訴小強，草原是一個極其穩定的生態系統。如果螞蚱滅絕了，小鳥照樣可以吃別的蟲子，所以一個物種的滅絕并不一定會引發重大的災難。

我們現在從專業一點的角度來看這個問題。我們用一種叫做食物網的有向圖來描述生物之間的關系：

一個食物網有N個點，代表N種生物，如果生物x可以吃生物y，那么從y向x連一個有向邊。

這個圖沒有環。

圖中有一些點沒有連出邊，這些點代表的生物都是生產者，可以通過光合作用來生存； 而有連出邊的點代表的都是消費者，它們必須通過吃其他生物來生存。

如果某個消費者的所有食物都滅絕了，它會跟著滅絕。
我們定義一個生物在食物網中的“災難值”為，如果它突然滅絕，那么會跟著一起滅絕的生物的種數。

如果小強和阿米巴把草原上所有的羊都給嚇死了，那么狼會因為沒有食物而滅絕，而小強和阿米巴可以通過吃牛、牛可以通過吃草來生存下去。所以，羊的災難值是1。但是，如果草突然滅絕，那么整個草原上的5種生物都無法幸免，所以，草的災難值是4。

給定一個食物網，你要求出每個生物的災難值。

輸入輸出格式

輸入格式：
輸入文件 catas.in 的第一行是一個正整數 N，表示生物的種數。生物從 1 標
號到 N。
接下來 N 行，每行描述了一個生物可以吃的其他生物的列表，格式為用空
格隔開的若干個數字，每個數字表示一種生物的標號，最后一個數字是 0 表示列表的結束。

輸出格式：
輸出文件catas.out包含N行，每行一個整數，表示每個生物的災難值。

輸入輸出樣例

輸入樣例#1：
5
0
1 0
1 0
2 3 0
2 0

輸出樣例#1：
4
1
0
0
0

【數據規模】

對50%的數據，N ≤ 10000。

對100%的數據，1 ≤ N ≤ 65534。

輸入文件的大小不超過1M。保證輸入的食物網沒有環。

分析：首先，把食物網按從獵物到捕食者的順序拓撲排序。依照top的序列構建滅絕樹，
依次考慮每個生物i：假設我們已經構建好了排序在i之前的生物組成的“滅絕樹”了。
假設i的食物有x[0]~x[k]（x[0]~x[k]在拓撲排序中比i靠前），
很顯然，只有x[0]~x[k]在樹上的公共祖先的滅絕會導致i滅絕，否則i一定可以找到能讓它活下來的食物。
于是，我們可以把i掛在x[0]~x[k]的最近公共祖先下面。
處理完所有的生物，我們得到的樹就是整個圖的滅絕樹了。之后dfs計算一下每個節點對應的子樹大小，子樹大小-1即危險程度

注意：在利用倍增求LCA，維護爸爸時，我提供了兩種寫法，然而我發現我自己yy的寫法（靠上的那個）要快，O(∩_∩)O~

這里寫代碼片 #include<cstdio> #include<cstring> #include<iostream> #include<cmath>using namespace std;const int N=65540; struct node{int x,y,next; }; node way[N*4],way1[N*4],tree[N*4]; int in[N],out[N]; int sta[N],st[N],tot=0,tou,wei,tot1=0,st1[N],tot2=0,st2[N]; int ans[N],fa[N][40],n,deep[N],unit;void add(int u,int v) {tot++;way[tot].x=u;way[tot].y=v;way[tot].next=st[u];st[u]=tot;return; }void add1(int u,int v) {tot1++;way1[tot1].x=u;way1[tot1].y=v;way1[tot1].next=st1[u];st1[u]=tot1;return; }void add2(int u,int v) {tot2++;tree[tot2].x=u;tree[tot2].y=v;tree[tot2].next=st2[u];st2[u]=tot2;return; }void top() //拓撲排序 {int i,j,tt=0;tou=0;wei=1;for (i=1;i<=n;i++)if (!in[i])sta[wei++]=i,tt++;while (tt<n){int r=sta[++tou];for (i=st[r];i;i=way[i].next){in[way[i].y]--;if (in[way[i].y]==0){sta[wei++]=way[i].y;in[way[i].y]=N;tt++;}}}return; }int LCA(int u,int v) {int i;if (u==v) return u;if (deep[u]<deep[v]) swap(u,v); //默認u為較深的 int d=deep[u]-deep[v]; if (d) //不在同一深度 for (i=0;d;i++,d>>=1) //d轉化為二進制 if (d&1) //這一位上是1 u=fa[u][i]; //向上跳if (u==v) return u;for (i=unit;i>=0;i--)if (fa[u][i]!=fa[v][i]){u=fa[u][i];v=fa[v][i];} return fa[u][0]; //直到跳到只有一步就重合了 ，返回 }void dfs(int x) //dfs利用滅絕樹求子樹size {ans[x]=1;int i;for (i=st2[x];i;i=tree[i].next){dfs(tree[i].y);ans[x]+=ans[tree[i].y];} }int main() {scanf("%d",&n);for (int i=1;i<=n;i++){int u;scanf("%d",&u);while (u){out[u]++;in[i]++;add(u,i);add1(i,u); //add用來top，add1用來添加反向變，輔助lca的求解 scanf("%d",&u);}}top();unit=log(n)/log(2)+1;for (int i=1;i<=n;i++) //整個過程都要依靠top的結果~~~,從前向后 {int x=way1[st1[sta[i]]].y;for (int j=st1[sta[i]];j;j=way1[j].next) //通過反向邊 x=LCA(x,way1[j].y); //尋找第i種生物所有食物的LCA add2(x,sta[i]); //i成為lca的兒子,建滅絕樹 fa[sta[i]][0]=x; deep[sta[i]]=deep[x]+1; //不要忘了維護深度 for (int l=1;fa[fa[sta[i]][l-1]][l-1];l++) //維護倍增的爸爸,[]有點多，容易搞暈 fa[sta[i]][l]=fa[fa[sta[i]][l-1]][l-1]; //for (int k=x,l=0;fa[k][l];k=fa[k][l++]) 網上一個神犇的寫法 //fa[sta[i]][l+1]=fa[k][l]; 這樣的寫法本蒟蒻這第一次見，nuibility }dfs(0);for (int i=1;i<=n;i++)printf("%d\n",ans[i]-1);return 0; }

轉載于:https://www.cnblogs.com/wutongtong3117/p/7673637.html

總結

以上是生活随笔為你收集整理的P2597 [ZJOI2012]灾难（top+lca）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。