P2597 [ZJOI2012]灾难

#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
#include <cstring>
const int N = 65534 + 1;
using namespace std;
int n;
namespace LCA
{
    vector < int > to [ N ];
    int fa [ N ] [ 17 ] ;
    int dep [ N ];
    void add ( int x , int y )
    {
        to [ x ] . push_back ( y );
        fa [ y ] [ 0 ] =x;
        for ( int i = 1; i <= 16; i ++ )
            fa [ y ] [ i ] = fa [ fa [ y ] [ i - 1 ] ] [ i - 1 ];
        dep [ y ] = dep [ x ] + 1;
    }
    int LCA ( int x , int y )
    {
        if ( dep [ x ] < dep [ y ] ) swap ( x , y );
        for ( int  i = 16; i >= 0; i -- )
        {
            if ( dep [ fa [ x ] [ i ] ] >= dep [ y ] )
                x = fa [ x ] [ i ];
        }
        if ( y == x ) return x;
        for ( int i = 16; i >= 0 ; i -- )
        {
            if ( fa [ x ] [ i ] != fa [ y ] [ i ] )
            {
                x = fa [ x ] [ i ];
                y = fa [ y ] [ i ] ;
            }
        }
        return fa [ x ] [ 0 ];
    }
    int Size [ N ];
    void dfs ( int x )
    {
        Size [ x ] = 1;
        for ( auto y : to [ x ] )
        {
            dfs ( y );
            Size [ x ] += Size [ y ] ;
        }
    }
    void print()
    {
        dfs( 0 );
        for ( int i = 1; i <= n ; i ++ )
        {
            cout << Size [ i ] - 1 << endl;
        }
    }
}
namespace topo
{
    vector < int > to [ N ];
    vector < int > fan [ N ];
    int in [ N ];
    void add ( int x , int y )
    {
        to [ x ] . push_back ( y );
        in [ y ] ++;
        fan [ y ] . push_back ( x );
    }
    queue < int > que;
    void topo ()
    {
        que . push ( 0 );
        for ( int i = 1; i <= n; i ++ )
            if ( in [ i ] == 0 )
            add ( 0 , i );
        while ( ! que . empty () )
        {
            int x = que . front () ; que . pop ( ) ;
            int lca = - 1 ;
            for ( auto y : fan [ x ] )
            {
                if ( lca == -1 )
                    lca = y ;
                else
                    lca = LCA :: LCA ( lca , y );
            }
            //cout << x << " " << lca << endl;
            if ( lca >= 0 )
            LCA :: add ( lca , x );
            for ( auto y : to [ x ] )
            {
                //cout << x << " " << y << endl;
                if ( -- in [ y ] == 0 ) que . push ( y );
            }
        }
    }
}
int main()
{
    freopen ( "text.in" , "r" , stdin );
    cin >> n;
    for ( int i = 1; i <= n; i ++ )
    {
        int x ;
        while ( cin >> x )
        {
            if ( x == 0 )
                break;
            else
                topo :: add ( x , i );
        }
    }
    topo :: topo ();
    LCA :: print();
    return 0;
}