slotenmaker.cpp

#include <iostream>

int main(void);


// Yes I know they have the same value, but the name is different
#define _UNDEF ( (uint32_t) ~0 )
#define _DONE  ( (uint32_t) ~0 )


// Quick and easy bitwise check if x is not _DONE
#define ISNTDONE(x) ( (uint32_t) ~x )



int main(void) {
  // uint32_t is range 0 - 4_294_967_295 so should be enough to save the numbers of the villages
  uint32_t villageCount, startVillage;

  std::cin >> villageCount >> startVillage;

  // 1-based should be 0-based
  --startVillage;

  uint32_t roadCount = villageCount-1;

  // All distances of villages ( Always <= 100_000 )
  // NOTE: Don't use villageCount as C++ doesn't like Variable-Length Arrays
  uint32_t distances[100000];

  // Initalise array with undefined value
  for(uint32_t i=0; i < villageCount; ++i) {
    distances[i] = _UNDEF;
  }

  // Set distance to start of the starting village to 0
  distances[startVillage] = 0;

  // Define array in which all the connections will be stored

  // NOTE: villageCount could be replaced with 100_000, but to avoid memory struggles
  //       and because C(++) doesn't mind in this case, just keep the variable
  uint32_t connections[villageCount][2];

  // Read all roads
  for (uint32_t i=0; i < roadCount; ++i) {
    std::cin >> connections[i][0] >> connections[i][1];

    // 1-based to 0-based
    --connections[i][0];
    --connections[i][1];
  }


  // Define maximal distance from the starting village
  uint32_t villagesConnected = 1;
  uint32_t maxDistance = 0;

  while ( villagesConnected < villageCount ) {
    // Go through all connections
    for (uint32_t i=0; i < roadCount; ++i) {
      // Get both villages from the connections
      // NOTE: Pointers are 32 bits too, so there is no benefit in using pointers here
      uint32_t vila = connections[i][0];
      uint32_t vilb = connections[i][1];

      uint32_t parent, child;

      // Don't double process anything
      if ( ISNTDONE(vila) && ISNTDONE(vilb) ) {
        // Check for the item that already has a parent
        if ( distances[vila] != _UNDEF ) {
          parent = vila;
          child  = vilb;
        } else if ( distances[vilb] != _UNDEF ) {
          parent = vilb;
          child  = vila;
        } else {
          // Not sure when this happens, but just continue
          continue;
        }

        distances[child] = distances[parent] + 1;
        ++villagesConnected;

        if ( distances[parent] == maxDistance ) {
          ++maxDistance;
        }

        connections[i][0] = _DONE;
        connections[i][1] = _DONE;
      }
    }
  }

  // Print (double the number of roads - the maximum distance) times three because of the locks
  std::cout << ( 2*roadCount - maxDistance ) * 3 << std::endl;
}