题目传送门
sol:树形dp,用$dp[u]$表示节点$u$代表的子树合法染色方案的数量,若$u$节点是黑色,则所有儿子随意,产生的方案数为$\prod dp[v], v \in son[u]$;若$u$节点是白色,则含有黑节点的儿子最多只能有一个,也可以没有。因为$dp[v]$里必有一种方案是整颗$v$子树均为白色,所有产生的方案数为$1 + \sum {dp[v] - 1}, v \in son[u]$。两者相加即为$dp[u]$。
- 树形dp
#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int, int> PII; const int MAXN = 1000010; const int MOD = 1000000007; inline int read() { int n = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -f; c = getchar(); } while (c >= '0' && c <= '9') { n = 10 * n + (c ^ '0'); c = getchar(); } return f * n; } struct { int v, to; } edge[2 * MAXN]; int head[MAXN], total; int dp[MAXN], que[MAXN]; void add_edge(int u, int v) { edge[total].v = v; edge[total].to = head[u]; head[u] = total ++; } void slove(int u) { int l = 0, r = -1; que[++r] = u; while (l <= r) { u = que[l++]; dp[u] = -1; for (int i = head[u]; i != -1; i = edge[i].to) { int v = edge[i].v; if (dp[v] != -1) que[++r] = v; } } while (r >= 0) { u = que[r--]; int tmp1 = 1, tmp2 = 1; for (int i = head[u]; i != -1; i = edge[i].to) { int v = edge[i].v; if (dp[v] == -1) continue; tmp1 = 1LL * tmp1 * dp[v] % MOD; tmp2 = (tmp2 + dp[v] - 1) % MOD; } dp[u] = (tmp1 + tmp2) % MOD; } } int main() { int n = read(); memset(head, -1, sizeof(head)); for (int i = 2; i <= n; i++) { int u = read(), v = read(); add_edge(u, v), add_edge(v, u); } slove(1); printf("%d\n", dp[1]); return 0; }
------------------------------------------------------------分隔线------------------------------------------------------------
总结:这道神奇的题目居然卡空间,一开始用vector存图 + dfs递归提交内存超限,改了bfs迭代形式就过了。赛后看了讨论群他们说这是卡vector存图,然鹅我居然在其他地方优化空间。不过这也让我意识到了递归,迭代,前向星和vector在效率上的区别。递归快,迭代省内存,前向星时间空间都优于vector。