BZOJ 2815 LCA

题

给一个DAG，问删掉每一个点后会导致多少个点不可达。

解

orzfhq
据说是支配树的弱化版……
完全不会做。看了题解看懂了然后<s>抄</s>打了一遍。
首先拓扑排序。定义灭绝树的概念是一个点消失后，其后代所有节点同时灭绝。
考虑增量法建这样的树。X_n的食物必然已经在树里了。求所有事物的LCA后把点连在上面。易有若连在LCA的某个后代则必有一种食物关系使得该节点消失后仍不会灭绝。
就这个样子啦。

码（14116 kb 260 ms）

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
const int maxn = 1e5 + 100;
struct E{int v, n;} e[maxn << 2];
int h[maxn], ecnt = 1, h2[maxn];
inline void add_edge(int u, int v){e[ecnt] = (E){v, h[u]}; h[u] = ecnt++; e[ecnt] = (E){u, h2[v]}; h2[v] = ecnt++;}
int depth[maxn] = {0}, ind[maxn] = {0}, fa[maxn][20];
int getlca(int u, int v)
{
    if(depth[u] < depth[v]) swap(u, v);
    int delta = depth[u] - depth[v];
    for(int i = 0; i < 20; i++) if((1 << i) & delta) u = fa[u][i];
    if(u == v) return u;
    for(int i = 19; ~i; i--) if(fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
    return fa[u][0];
}
int ans[maxn] = {0}, s[maxn] = {0};
int main()
{
    int n; read(n);
    for(int i = 1; i <= n; i++)
    {
        int j; while(read(j), j) add_edge(i, j), ind[i]++;
    }
    int l = 0, r = 0;
    for(int i = 1; i < n; i++) if(!ind[i]) s[r++] = i;
    for(int l = 0; l < r; l++) for(int j = h2[s[l]]; j; j = e[j].n)
    {
        ind[e[j].v]--; if(!ind[e[j].v]) s[r++] = e[j].v;
    }
    depth[0] = 0;
    for(int i = 1; i <= n; i++)
    {
        if(!h[s[i]])
        {
            fa[s[i]][0] = 0, depth[s[i]] = 1;
            continue;
        }
        int lca = e[h[s[i]]].v;
        for(int j = e[h[s[i]]].n; j; j = e[j].n)
            lca = getlca(lca, e[j].v);
        depth[s[i]] = depth[lca] + 1;
        int cur = 0;
        fa[s[i]][cur] = lca;
        ind[lca]++;
        for(; fa[s[i]][cur]; cur++)
            fa[s[i]][cur + 1] = fa[fa[s[i]][cur]][cur];
    }
    l = r = 0;
    for(int i = 1; i <= n; i++)
    {
        ans[i] = 1;
        if(!ind[i]) s[r++] = i;
    }
    for(; l < r; l++)
    {
        ind[fa[s[l]][0]]--;
        ans[fa[s[l]][0]] += ans[s[l]];
        if(!ind[fa[s[l]][0]]) s[r++] = fa[s[l]][0];
    }
    for(int i = 1; i <= n; i++) printf("%d\n", ans[i] - 1);
    return 0;
}