Submission #1338423

---

Source Code Expand

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

const int DIM = 2e5 + 5;

deque<pair<int, int>> que;
vector<int> edg[DIM], axe[DIM];

int lev[DIM], fth[DIM];
bool oki[DIM], mrk[DIM];

void dfs( int x, int f ) {
    lev[x] = lev[f] + 1; fth[x] = f;
    
    for( int y : edg[x] )
        if( y != f )
            dfs( y, x );
    
    return;
}

int main( void ) {
    
    int n, x, y;
    cin >> n >> x >> y;
    
    for( int i = 2; i <= n; i ++ ) {
        int x, y;
        cin >> x >> y;
        
        axe[x].push_back( y );
        axe[y].push_back( x );
    }
    
    for( int i = 2; i <= n; i ++ ) {
        int x, y;
        cin >> x >> y;
        
        edg[x].push_back( y );
        edg[y].push_back( x );
    }
    
    lev[0] = -1; dfs( y, 0 );
    for( int i = 1; i <= n; i ++ ) {
        for( int j : axe[i] ) {
            bool ok = true;
            int x = i, y = j;
            
            if( lev[x] > lev[y] )
                swap( x, y );
            
            if( fth[x] == fth[y] ) ok = false;
            if( fth[fth[y]] == x ) ok = false;
            if( fth[y] == x )      ok = false;
            
            if( ok == true )
                oki[x] = oki[y] = true;
        }
    }
    
    mrk[x] = true; int ans = 0;
    que.push_back( make_pair( x, 0 ) );
    for( ; que.empty() == false; que.pop_front() ) {
        pair<int, int> x = que.front();
        ans = max( ans, lev[x.first] * 2 );
        
        if( oki[x.first] == true )
            ans = 1e9;
        
        for( int y : axe[x.first] ) {
            if( mrk[y] == 1 || x.second + 1 >= lev[y] )
                continue;
            
            mrk[y] = true;
            que.push_back( make_pair( y, x.second + 1 ) );
        }
    }
    
    if( ans == 1e9 )
        ans = -1;
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result