P2597 [ZJOI2012]灾难

题目描述

见链接

Solution

建立支配树即可

Addition

步骤:

反向建边

拓扑排序

按反拓扑序依次加入支配树节点

加入节点时, 取其所有原图父亲的 $LCA$ 作新树的父亲

Attention

两个字符 $1,0$ 调了 $6-hours$ !!!
要时刻注意循环边界 !!!

Code

#include<bits/stdc++.h>
#define reg register

const int maxn = 80000;

int N, cnt, num0, Lim;
int B[maxn], In[maxn];
int F[maxn][18];
int dep[maxn];
int head[maxn];
int size[maxn];

struct Edge{ int nxt, to; } edge[maxn<<1];

void Add(int from, int to){
        edge[++ num0] = (Edge){ head[from], to };
        head[from] = num0;
}

int LCA(int a, int b){
        if(dep[a] < dep[b]) std::swap(a, b);
        for(reg int i = 17; i >= 0; i --)
                if(dep[F[a][i]] >= dep[b]) a = F[a][i];
        if(a == b) return a;
        for(reg int i = 17; i >= 0; i --)
                if(F[a][i] != F[b][i]) a = F[a][i], b = F[b][i];
        return F[a][0];
}

void DFS(int k, int fa){
        size[k] = 1;
        for(reg int i = head[k]; i; i = edge[i].nxt){
                if(i <= Lim) continue ;
                int to = edge[i].to;
                if(to == fa) continue ;
                DFS(to, k);
                size[k] += size[to];
        }
}

int main(){
        scanf("%d", &N);
        for(reg int i = 1; i <= N; i ++){
                int x;
                scanf("%d", &x);
                while(x) Add(i, x), In[x] ++, scanf("%d", &x);
        }
        Lim = num0;
        std::queue <int> Q;
        for(reg int i = 1; i <= N; i ++) if(!In[i]) Q.push(i);
        while(!Q.empty()){
                int ft = Q.front(); Q.pop();
                B[++ cnt] = ft;
                for(reg int i = head[ft]; i; i = edge[i].nxt){
                        int to = edge[i].to;
                        if(!(-- In[to])) Q.push(to); 
                }
        }
        dep[N+1] = 1;
        for(reg int i = 0; i <= 17; i ++) F[N+1][i] = N+1;
        for(reg int i = cnt; i >= 1; i --){
                int s = N+1, x = B[i];
                if(head[x]){
                        s = edge[head[x]].to;
                        for(reg int j = head[x]; j; j = edge[j].nxt) 
                                s = LCA(s, edge[j].to);
                }
                dep[x] = dep[s] + 1, F[x][0] = s;
                Add(s, x);
                for(reg int j = 1; j <= 17; j ++) F[x][j] = F[F[x][j-1]][j-1];
        }
        DFS(N+1, 0);
        for(reg int i = 1; i <= N; i ++) printf("%d
", size[i] - 1);
        return 0;
}