Cod sursa(job #1710479)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 29 mai 2016 00:18:48
Problema Revolta Scor 100
Compilator cpp Status done
Runda Arhiva ICPC Marime 7.26 kb
/*
 Definitia:
 
 C[node]   = costul nodului node
 Dp1[node] = lantul 'in jos' de cost maxim
 Dp2[node] = lantul 'in sus' de cost maxim
 Dp3[node] = lantul de cost maxim din subarborele lui node
 Dp4[node] = lantul de cost maxim din afara subarborelui lui node
 
 Recurenta:
 
 Dp1[node] = C[node] + max( Dp1[son_node] )
 Dp2[node] = D[node] + max( Dp2[father_node], C[father_node] + Dp1[brother_node] )
 Dp3[node] = max( Dp3[son_node], C[node] + Dp1[son_node1] + Dp1[son_node2] )
 Dp4[node] = max( Dp4[father_node], Dp3[brother_node], Dp2[father_node] + Dp1[brother_node] )
 */
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>

const int DIM = 1 << 17;
const int INF = 0x3f3f3f3f;
using namespace std;

int Dp1[DIM], Dp2[DIM], Dp3[DIM], Dp4[DIM], C[DIM], V[DIM], Dst[DIM], Ddr[DIM], minim, T;
int N, M, Father[DIM]; vector <int> Edge[DIM]; struct edge{ int x, y; } E[DIM];

void DFS1( int node, int father ) {
    Dp1[node] = max( Dp1[node], C[node] ); Father[ node ] = father;
    
    for( vector <int> :: iterator it = Edge[node].begin(); it != Edge[node].end(); it ++ ) {
        int next_node = *it;
        
        if( next_node != father ) {
            DFS1( next_node, node );
            Dp1[node] = max( Dp1[node], C[node] + Dp1[next_node] );
        }
    }
    
    return;
}

void DFS2( int node, int father ) {
    Dp2[node] = max( Dp2[node], C[node] );
    
    int K = 0;
    for( vector <int> :: iterator it = Edge[node].begin(); it != Edge[node].end(); it ++ ) {
        int next_node = *it;
        
        if( next_node != father )
            V[++K] = next_node;
    }
    
    Dst[0] = 0;
    for( int i = 1; i <= K; i ++ )
        Dst[i] = ( (Dp1[ V[i] ] < Dp1[ Dst[i - 1] ]) ? Dst[i - 1] : V[i] );
    
    Ddr[K + 1] = 0;
    for( int i = K; i >= 1; i -- )
        Ddr[i] = ( (Dp1[ V[i] ] < Dp1[ Ddr[i + 1] ]) ? Ddr[i + 1] : V[i] );
    
    for( int i = 1; i <= K; i ++ )
        Dp2[ V[i] ] = max( Dp2[ V[i] ], C[ V[i] ] + max( Dp2[node], C[node] + max( Dp1[ Dst[i - 1] ], Dp1[ Ddr[i + 1] ] ) ) );
    
    for( vector <int> :: iterator it = Edge[node].begin(); it != Edge[node].end(); it ++ ) {
        int next_node = *it;
        
        if( next_node != father )
            DFS2( next_node, node );
    }
    
    return;
}

void DFS3( int node, int father ) {
    Dp3[node] =  max( Dp3[node], Dp1[node] );
    
    int maxim1 = 0, maxim2 = 0;
    for( vector <int> :: iterator it = Edge[node].begin(); it != Edge[node].end(); it ++ ) {
        int next_node = *it;
        
        if( next_node != father ) {
            DFS3( next_node, node );
            Dp3[node] = max( Dp3[node], Dp3[next_node] );
            
            if( maxim1 < Dp1[next_node] ) {
                maxim2 = maxim1;
                maxim1 = Dp1[next_node];
            } else
                if( maxim2 < Dp1[next_node] )
                    maxim2 = Dp1[next_node];
        }
    }
    
    Dp3[node] = max( Dp3[node], C[node] + maxim1 + maxim2 );
    return;
}

void DFS4( int node, int father ) {
    Dp4[node] = max( Dp4[node], Dp4[father] );
    
    int K = 0, maxim1 = 0, maxim2 = 0;
    for( vector <int> :: iterator it = Edge[node].begin(); it != Edge[node].end(); it ++ ) {
        int next_node = *it;
        
        if( next_node != father )
            V[++K] = next_node;
    }
    
    Dst[0] = 0;
    for( int i = 1; i <= K; i ++ )
        Dst[i] = ( (Dp1[ V[i] ] < Dp1[ Dst[i - 1] ]) ? Dst[i - 1] : V[i] );
    
    Ddr[K + 1] = 0;
    for( int i = K; i >= 1; i -- )
        Ddr[i] = ( (Dp1[ V[i] ] < Dp1[ Ddr[i + 1] ]) ? Ddr[i + 1] : V[i] );
    
    for( int i = 1; i <= K; i ++ )
        Dp4[ V[i] ] = max( Dp4[ V[i] ], Dp1[ Dst[i - 1] ] + Dp1[ Ddr[i + 1] ] + C[node] );
    
    maxim1 = 0; maxim2 = 0;
    for( int i = 1; i <= K; i ++ ) {
        Dp4[ V[i] ] = max( Dp4[ V[i] ], maxim1 + maxim2 + C[node] );
        
        if( maxim1 < Dp1[ V[i] ] ) {
            maxim2 = maxim1;
            maxim1 = Dp1[ V[i] ];
        } else
            if( maxim2 < Dp1[ V[i] ] )
                maxim2 = Dp1[ V[i] ];
    }
    
    maxim1 = 0; maxim2 = 0;
    for( int i = K; i >= 1; i -- ) {
        Dp4[ V[i] ] = max( Dp4[ V[i] ], maxim1 + maxim2 + C[node] );
        
        if( maxim1 < Dp1[ V[i] ] ) {
            maxim2 = maxim1;
            maxim1 = Dp1[ V[i] ];
        } else
            if( maxim2 < Dp1[ V[i] ] )
                maxim2 = Dp1[ V[i] ];
    }
    
    for( int i = 1; i <= K; i ++ )
        Dp4[ V[i] ] = max( Dp4[ V[i] ], Dp2[node] + max( Dp1[ Dst[i - 1] ], Dp1[ Ddr[i + 1] ] ) );
    
    Dst[0] = 0;
    for( int i = 1; i <= K; i ++ )
        Dst[i] = ( (Dp3[ V[i] ] < Dp3[ Dst[i - 1] ]) ? Dst[i - 1] : V[i] );
    
    Ddr[K + 1] = 0;
    for( int i = K; i >= 1; i -- )
        Ddr[i] = ( (Dp3[ V[i] ] < Dp3[ Ddr[i + 1] ]) ? Ddr[i + 1] : V[i] );
    
    for( int i = 1; i <= K; i ++ )
        Dp4[ V[i] ] = max( Dp4[ V[i] ], max( Dp3[ Dst[i - 1] ], Dp3[ Ddr[i + 1] ] ) );
    
    for( vector <int> :: iterator it = Edge[node].begin(); it != Edge[node].end(); it ++ ) {
        int next_node = *it;
        
        if( next_node != father )
            DFS4( next_node, node );
    }
    
    return;
}

class input_reader {
private:
    FILE *input_file;
    static const int SIZE = 1 << 17;
    char buffer[SIZE]; int cursor;
    
    inline void advance() {
        if( ++cursor == SIZE ) {
            cursor = 0;
            fread( buffer, SIZE, 1, input_file );
        }
        
        return;
    }
    
    inline char current() {
        return buffer[cursor];
    }
public:
    input_reader( const char *file_name, const char *file_type ) {
        input_file = fopen( file_name, file_type ); cursor = 0;
        fread( buffer, SIZE, 1, input_file );
    }
    
    input_reader &operator >>( int &value ) {
        value = 0;
        
        while( current() < '0' || current() > '9' )
            advance();
        
        while( current() >= '0' && current() <= '9' ) {
            value = value * 10 + ( current() - '0' );
            advance();
        }
        
        return *this;
    }
} input_file( "revolta.in", "r" );
FILE *output_file = fopen( "revolta.out", "w" );

int main() {
    
    input_file >> T;
    
    for( int t = 1; t <= T; t ++ ) {
        input_file >> N;
        
        memset( Dp1, 0, sizeof(Dp1) );
        memset( Dp2, 0, sizeof(Dp2) );
        memset( Dp3, 0, sizeof(Dp3) );
        memset( Dp4, 0, sizeof(Dp4) );
        
        for( int i = 0; i < DIM; i ++ )
            Edge[i].resize(0);
        
        for( int i = 1; i <= N; i ++ )
            C[i] = 1;
        
        for( int i = 1; i < N; i ++ ) {
            input_file >> E[i].x >> E[i].y;
            
            E[i].x++; E[i].y++;
            
            Edge[ E[i].x ].push_back( E[i].y );
            Edge[ E[i].y ].push_back( E[i].x );
        }
        
        DFS1( 1, 0 ); DFS2( 1, 0 );
        DFS3( 1, 0 ); DFS4( 1, 0 );
        
        minim = Dp3[1] - 1;
        for( int i = 1; i < N; i ++ ) {
            if( Father[ E[i].x ] == E[i].y )
                swap( E[i].x, E[i].y );
            
            //minim = min( minim, Dp3[ E[i].y ] / 2 + Dp4[ E[i].y ] / 2 + 1 );
            minim = min( minim, max( max( Dp3[ E[i].y ] - 1, Dp4[ E[i].y ] - 1 ), Dp3[ E[i].y ] / 2 + Dp4[ E[i].y ] / 2 + 1 ) );
        }
        
        fprintf( output_file, "%d\n", minim );
        
    }
    
    return 0;
}