ABC036 D 塗り絵

http://abc036.contest.atcoder.jp/tasks/abc036_d
　木を白と黒で塗るのですが、両端が黒の辺があってはいけません。さて何通りの塗り方があるでしょうか、という問題。本番では木になることすらわかりませんでしたが公式解説が神だったのですんなり解けました。正直スライド時代より現在のホワイトボード＋pdfのほうが1000000007倍くらいわかりやすいしもう一生ついていきますという感じです。
　頂点xを根とする部分木を考え、この部分木の塗り方をdp[x]通り、xが白いとき（＝xの子が何色でもいいとき）の塗り方をdp2[x]通りとします。さらに、ｘの子をy1...ykとします。このとき、dp2[x]は子の塗り方がなんでもいいのでdp2[x] = dp[y1]*...*dp[yk]通りです。これにxが黒い時の場合の数をたせばいいのですが、これはxの子が白い時の場合の数の掛けあわせでdp2[y1]*...*dp2[yk]通りです。これらを根（どこでもよい）から遠い辺から計算すれば解けます。

const int MAX_V = 100010;
vector<int> edge[MAX_V];
ll dp[MAX_V], dp2[MAX_V];
void dfs(int p, int x){
    vector<int> child;
    for(int t : edge[x]) if(t != p) child.push_back(t);
    for(int t : child) dfs(x, t);
    ll prod = 1;
    for(int t : child) prod = prod * dp[t] % MOD;
    dp2[x] = prod; prod = 1;
    for(int t : child) prod = prod * dp2[t] % MOD;
    dp[x] = (dp2[x] + prod) % MOD;
}
int main(){
    int n; cin >> n;
    rep(i, n - 1){
        int a, b; cin >> a >> b;
        a--; b--;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    dfs(-1, 0);
    cout << dp[0] << endl;
    return 0;
}

とてもきれいに解けて良さがある問題だなあと思いました。
初見とはいえこのくらいは本番でも解けないとダメですね。反省。