第６回日本情報オリンピック 本選 「最軽量のモビール」

ひとつ前の「最悪の記者」のほうが少し難易度が高いきがする。

部分点解法全く思いつきませんでしたすいません。

• 満点解法

深さ優先探索(DFS)をする.

まず一番上にあるモビール（？）をもとめる。
そのモビールを関数dfsに投げる
関数dfsはそのモビールに必要な最小のおもりの質量を返す関数
p:qについて、通分的なのできたらする。
そして再帰的に赤と青の必要な最小のおもりを再帰的に求めて計算して答えを返す。

計算量よくわからないけど00.00sだったので問題ない。

#include <cstdio>

using namespace std;
int n,d[102][4];
bool ch[102];

int gcd(int a,int b){
  if(b == 0) return a;
  return gcd(b,a % b);
}


int dfs(int x){
  int p = d[x][0];
  int q = d[x][1];
  int w = gcd(p,q);
  
  p /= w;
  q /= w;
  
  if(d[x][2] == 0 && d[x][3] == 0){
    return (p+q);
  }
  
  int red=1,blue=1;
  
  if(d[x][2] != 0) red = dfs(d[x][2]);
  if(d[x][3] != 0) blue = dfs(d[x][3]);
  
  int k = p * red;
  int h = q * blue;
  int i = 0;
  int j = 0;
  while(1){
    i++;
    if(k * i % h == 0){
      j = k * i / h;
      break;
    }
  }
  
  return (i*red+j*blue);
}
  

int main(){

  scanf("%d",&n);

  for(int i = 1;i <= n;i++){
    ch[i] = false;
  }
  
  for(int i = 1;i <= n;i++){
    for(int j = 0;j < 4;j++){
      scanf("%d",&d[i][j]);
      if(j == 2 || j == 3){
	ch[d[i][j]] = true;
      }
    }
  }
  int ans;
  for(int i = 1;i <= n;i++){
    if(ch[i] == false){
      ans = i;
    }
  }
  
  printf("%d\n",dfs(ans));

  return 0;
  
}