SRM 58５ Div2 MediumTrafficCongestionDivTwo

問題

完全２分木がある。すべての頂点を一度だけ通るような最小パス被覆のサイズを求めよ。木の高さは60以下

やりかた

という感じで3つのノードでひとつのパスというふうにした時パス数は最小となる。
なのでceil(頂点数/3)。

以下ソース。

class TrafficCongestionDivTwo {
public:
  ll powll(int a, int n){
    ll ret = 1;
    for(int i = 0; i < n; i++) ret *= a;
    return ret;
  }
  long long theMinCars(int treeHeight) {
    return (ll)((powll(2, treeHeight + 1) + 1) / 3);
  }
};