SRM585 Div1 Easy

250
http://community.topcoder.com/stat?c=problem_statement&pm=11361

ある頂点とその直接の子2つを移動する様な選び方が最適なはず。つまり、頂点3個毎を1塊。
木の頂点を高さごとに分けて考えたとして、根とその直接の親の部分のコストを付け足す様な DP になる。

class TrafficCongestion {
public:
  int theMinCars(int treeHeight)
  {
    const lli mod = 1000000007;

    const int N = 1000000 + 10;
    static lli p2[N];
    p2[0] = 1;
    for (int i = 1; i < N; ++i) {
      p2[i] = p2[i - 1] * 2;
      p2[i] %= mod;
    }

    static lli dp[N];
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i < N; ++i) {
      dp[i] = (dp[i - 2] + p2[i - 1]) % mod;
    }

    return dp[treeHeight];
  }
};