백준 27915 - 금광

https://www.acmicpc.net/problem/27915

 

문제에서 가장 중요한 점은 한 기업은 최대 2개의 노드만 소유할 수 있다는 것이다.

 

왜냐하면 3개 이상의 노드를 점유한다고 했을 때 각 노드가 홀수의 거리를 유지한다고 해도 양 끝의 노드의 거리가 짝수가 되기 때문이다.

 

따라서 각 기업은 무조건 홀수 레벨에서 짝수 레벨로만 연결할 수 있고, 이는 색 $R, B$로 구성된 이분그래프로 표현할 수 있다.

 

이렇게 이분그래프를 만들었을 때 $max(|R|, |B|)$가 정답이 된다.

 

정답 코드

#pragma GCC target("fma,avx,avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
 
using namespace std;
using namespace __gnu_pbds;
 
using ll = int_fast64_t;
using pii = pair<int, int>;
// using oset = tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;
 
constexpr int MXN = 1e5+1;
int n;
vector<int> tr[MXN];
int odd, even;
 
void solve()
{
  cin >> n;
  for (int i = 2; i <= n; i++)
  {
    int par;
    cin >> par;
    tr[par].push_back(i);
  }
 
  queue<pii> q;
  q.push({1, 0});
  while (q.size())
  {
    auto [node, lvl] = q.front();
    q.pop();
 
    if (lvl & 1)
    {
      ++odd;
    }
    else
    {
      ++even;
    }
 
    for (int i : tr[node])
    {
      q.push({i, lvl + 1});
    }
  }
 
  cout << max(odd, even);
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}