[CF852E]Casinos and travel(2019-11-15考试)

题目大意

有一棵\(n\)个点的树，令\(f(u)\)表示给树黑白染色，满足以\(u\)为根的树中，每个叶子节点到根的路径上黑点数量为偶数的染色方案数，求\(\sum\limits_{u=1}^n f(u)\)

题解

可以发现，确定了非叶子节点后，可以通过调整叶子的颜色使得每种方案均成立。令\(leaf\)为叶子的个数，答案为\(2^{n-leaf}(n+leaf)\)

当然也可以通过树形\(\mathrm{dp}\)来解决，不过这样比较麻烦

卡点

无

C++ Code：

#include <cstdio>
#include <iostream>
#include <algorithm>
#define mul(a, b) (static_cast<long long> (a) * (b) % mod)
#define _mul(a, b) (a = static_cast<long long> (a) * (b) % mod)
const int maxn = 1e5 + 10, mod = 1e9 + 7;
int n, ans, deg[maxn], num;

inline int pw(int b, int p) {
    int r = 1;
    for (; p; p >>= 1, _mul(b, b)) if (p & 1) _mul(r, b);
    return r;
}
int main() {
    std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
    std::cin >> n;
    if (n == 1) return std::cout << "1\n", 0;
    for (int i = 1, a, b; i < n; ++i)
        std::cin >> a >> b, ++deg[a], ++deg[b];
    for (int i = 1; i <= n; ++i) num += deg[i] == 1;
    std::cout << mul(n + num, pw(2, n - num)) << '\n';
    return 0;
}