您當前位置：首頁 > php開源 > php教程 > 【BZOJ2815】【ZJOI2012】災難阿米巴和小強題動態倍增LCA 災難樹

【BZOJ2815】【ZJOI2012】災難阿米巴和小強題動態倍增LCA 災難樹

來源：程序員人生發布時間：2015-03-26 09:07:12 閱讀次數：3437次

題意：

原題面請見 ${JS}_{Shining}$ 博客

http://www.cnblogs.com/JS-Shining/archive/2013/01/12/2857429.html

題解：

我們構建1顆災害樹，使得1個節點的任意1個先人滅絕，則其會滅絕。
則可以依照拓撲序掃每一個節點，然后加入到災害樹中時只需要把它的父親賦成它所有食品的LCA就行了。
我們可以動態處理每一個節點的倍增lca數組 $f_{i,j}$ 表示i的第 $(1<<j)$ 高先人。

代碼：

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 70000
#define M 600000
#define LOGN 20
using namespace std;
struct KSD
{
    int v,next;
}e[M],E[M],Ee[M];
int head[N],cnt,HEAD[N],CNT,Head[N];
inline void add(int u,int v)
{
    e[++cnt].v=v;
    Ee[cnt].v=u;
    e[cnt].next=head[u];
    Ee[cnt].next=Head[v];
    Head[v]=head[u]=cnt;
}
inline void ADD(int u,int v)
{
    E[++CNT].v=v;
    E[CNT].next=HEAD[u];
    HEAD[u]=CNT;
}
int f[N][LOGN],dep[N];
int getlca(int a,int b)
{
    int i;
    if(dep[a]<dep[b])swap(a,b);
    for(i=LOGN-1;i>=0;i--)
        if(dep[f[a][i]]>=dep[b])a=f[a][i];
    if(a==b)return a;
    for(i=LOGN-1;i>=0;i--)
        if(f[a][i]!=f[b][i])
            a=f[a][i],b=f[b][i];
    return f[a][0];
}
int d[N],ans[N];
queue<int>q;
int dfs(int x)
{
    ans[x]=1;
    for(int i=HEAD[x];i;i=E[i].next)
        ans[x]+=dfs(E[i].v);
    return ans[x];
}
int n;
int main()
{
    int i,j,k;
    int a,b,c;
    int u,v,lca;

    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        while(scanf("%d",&a),a)
        {
            add(a,i);
            d[i]++;
        }
    }
    for(i=1;i<=n;i++)if(!d[i])add(n+1,i),d[i]=1;
    q.push(n+1);
    while(!q.empty())
    {
        u=q.front(),q.pop();
        lca=0;
        for(i=Head[u];i;i=Ee[i].next)
        {
            v=Ee[i].v;
            if(i==Head[u])lca=v;
            else lca=getlca(lca,v);
        }
        for(i=head[u];i;i=e[i].next)
        {
            d[v=e[i].v]--;
            if(!d[v])q.push(v);
        }
        if(lca)
        {
            ADD(lca,u),f[u][0]=lca;
            for(j=1;j<LOGN;j++)
                f[u][j]=f[f[u][j-1]][j-1];
        }
        dep[u]=dep[lca]+1;
    }
    dfs(n+1);
    for(i=1;i<=n;i++)printf("%d
",ans[i]-1);
    return 0;
}