BZOJ 2815: [ZJOI2012]灾难

呃，题面没了，大概就是给出一些生物之间的捕食关系，求灭绝树每个点的灾难值。

拓扑排序之后倒着加入点，动态维护fa[][]数组，倍增法求LCA，当然大佬愿意写动态树也是极好的……

 #include <cstdio>

 inline int nextChar(void) {

     const int siz = ;

     static char buf[siz];

     static char *hd = buf + siz;

     static char *tl = buf + siz;

     if (hd == tl)

         fread(hd = buf, , siz, stdin);

     return *hd++;

 }

 inline int nextInt(void) {

     register int ret = ;

     register int neg = false;

     register int bit = nextChar();

     for (; bit < ; bit = nextChar())

         if (bit == '-')neg ^= true;

     for (; bit > ; bit = nextChar())

         ret = ret *  + bit - ;

     return neg ? -ret : ret;

 }

 const int siz = ;

 int n;

 int cnt[siz];

 int tot1;

 int hd1[siz];

 int to1[siz];

 int nt1[siz];

 inline void add1(int u, int v)

 {

     nt1[tot1] = hd1[u]; to1[tot1] = v; hd1[u] = tot1++;

 }

 int tot2;

 int hd2[siz];

 int to2[siz];

 int nt2[siz];

 inline void add2(int u, int v)

 {

     nt2[tot2] = hd2[u]; to2[tot2] = v; hd2[u] = tot2++;

 }

 int dep[siz], fa[siz][];

 inline int lca(int a, int b)

 {

     if (a == -)

         return b;

     if (dep[a] < dep[b])

         a ^= b ^= a ^= b;

     for (int i = ; i >= ; --i)

         if (dep[fa[a][i]] >= dep[b])

             a = fa[a][i];

     if (a == b)

         return a;

     for (int i = ; i >= ; --i)

         if (fa[a][i] != fa[b][i])

             a = fa[a][i],

             b = fa[b][i];

     return fa[a][];

 }

 int que[siz], head, tail;

 int sz[siz];

 void dfs(int u)

 {

     for (int i = hd2[u]; ~i; i = nt2[i])

         dfs(to2[i]), sz[u] += sz[to2[i]];

     ++sz[u];

 }

 signed main(void)

 {

     n = nextInt();

     for (int i = ; i <= n; ++i)

         hd1[i] = hd2[i] = -;

     for (int i = , t; i <= n; ++i)

         while (t = nextInt(), t)

             add1(i, t), ++cnt[t];

     for (int i = ; i <= n; ++i)

         if (!cnt[i])que[tail++] = i;

     while (head != tail)

     {

         int u = que[head++], v;

         for (int i = hd1[u]; ~i; i = nt1[i])

             if (!(--cnt[v = to1[i]]))que[tail++] = v;

     }

     for (int i = tail - ; i >= ; --i)

     {

         int u = que[i], v = -;

         for (int j = hd1[u]; ~j; j = nt1[j])

             v = lca(v, to1[j]);

         if (v == -)v = ;

         add2(v, u);

         fa[u][] = v;

         dep[u] = dep[v] + ;

         for (int j = ; j < ; ++j)

             fa[u][j] = fa[fa[u][j - ]][j - ];

     }

     dfs();

     for (int i = ; i <= n; ++i)

         printf("%d\n", sz[i] - );

 }

@Author: YouSiki