CF1228F One Node is Gone

题目链接

问题分析

这题感觉就是有很多种方法，然后一种都写不明白……

首先分为3种情况：

可以从叶子向上一层一层处理。第一个情况比较好判断；剩下两种情况通过对应节点儿子的个数来判断。注意第二种情况叶节点最大深度差只能是1，其他的点不能有深度差（毕竟是完全二叉树）。

参考程序

#include <bits/stdc++.h>
//#include <unistd.h>
using namespace std;

const int Maxn = 131100;
struct edge {
    int To, Next;
    edge() {}
    edge( int _To, int _Next ) : To( _To ), Next( _Next ) {}
};
edge Edge[ Maxn << 1 ];
int Start[ Maxn ], Used;
inline void AddEdge( int x, int y ) {
    Edge[ ++Used ] = edge( y, Start[ x ] );
    Start[ x ] = Used;
    return;
}
int deep, n;
int Deg[ Maxn ], Dep[ Maxn ], Deep, Son[ Maxn ];
int Rec[ Maxn ], Left, Vis[ Maxn ];
int Ans[ 10 ];

int main() {
    scanf( "%d", &deep );
    n = 1; for( int i = 1; i <= deep; ++i ) n *= 2; n -= 2;
    memset( Deg, 0, sizeof( Deg ) );
    for( int i = 1; i < n; ++i ) {
        int x, y;
        scanf( "%d%d", &x, &y );
        AddEdge( x, y );
        AddEdge( y, x );
        ++Deg[ x ]; ++Deg[ y ];
    }

    Left = n;
    Deep = 1;
    for( int i = 1; i <= n; ++i )
        if( Deg[ i ] == 1 )
            Dep[ i ] = Deep;

    while( Left > 1 ) {
        //printf( "========================================\n" );
        //printf( "Deg B:\n" );
        //for( int i = 1; i <= n; ++i ) printf( "%d ", Deg[ i ] );
        //printf( "\n" );
        Rec[ 0 ] = 0;
        for( int i = 1; i <= n; ++i )
            if( Deg[ i ] == 1 ) {
                Rec[ ++Rec[ 0 ] ] = i;
                if( Son[ i ] != 3 && Dep[ i ] != Deep ) {
                    printf( "0\n" );
                    return 0;
                }
                if( Son[ i ] == 3 && Dep[ i ] + 1 != Deep ) {
                    printf( "0\n" );
                    return 0;
                }
                if( Son[ i ] != 2 && Son[ i ] != 0 ) {
                    if( Ans[ 0 ] ) {
                        printf( "0\n" );
                        return 0;
                    }
                    Ans[ ++Ans[ 0 ] ] = i;
                }
            }
        //printf( "Rec %d\n", Rec[ 0 ] );
        //for( int i = 1; i <= Rec[ 0 ]; ++i ) printf( "%d ", Rec[ i ] );
        //printf( "\n" );

        if( Rec[ 0 ] == 2 && Left == 2 ) {
            if( Ans[ 0 ] ) {
                printf( "0\n" );
                return 0;
            }
            printf( "2\n%d %d\n", Rec[ 1 ], Rec[ 2 ] );
            return 0;
        }

        for( int i = 1; i <= Rec[ 0 ]; ++i )
            Vis[ Rec[ i ] ] = 1;

        for( int i = 1; i <= Rec[ 0 ]; ++i ) {
            int u = Rec[ i ];
            for( int t = Start[ u ]; t; t = Edge[ t ].Next ) {
                int v = Edge[ t ].To;
                if( Vis[ v ] ) continue;
                --Deg[ u ]; --Deg[ v ];
                ++Son[ v ];
                if( Dep[ v ] == 0 ) Dep[ v ] = Deep + 1;
            }
        }

        Left -= Rec[ 0 ];
        ++Deep;
        //printf( "Deg A:\n" );
        //for( int i = 1; i <= n; ++i ) printf( "%d ", Deg[ i ] );
        //printf( "\n" );
        //printf( "Left = %d\n", Left );
        //printf( "Son:\n" );
        //for( int i = 1; i <= n; ++i ) printf( "%d ", Son[ i ] );
        //printf( "\n" );
        //printf( "Ans = %d\n", Ans[ 0 ] );
        //sleep( 3 );
    }

    printf( "1\n%d\n", Ans[ 1 ] );

    return 0;
}