题目链接： SPOJ Con-Junctions 题意： 给一个 n 个节点和n−1条边的树，要用灯点亮所有的边，每条边至少要有一个端点放盏灯就点亮了这条边，求最少的放灯数量和最少放灯数量时的方案数。方案数结果模 10007 输出。 数据范围： n≤100010 分析： 最少放灯数量很好求。 用 dp[u][0] 表示点亮 u 子树的所有边时且u节点不放灯的最少数量，用 dp[u][1] 表示点亮 u 子树的所有边时且u节点放灯时的最少数量。 状态转移方程：
dp[u][0]=∑dp[v][1],v是u的所有儿子 dp[u][1]=1+∑min(dp[v][0],dp[v][1])，v是u的所有儿子 那么我们接着用 cnt[u][0] 和 cnt[u][1] 表示对应 dp[u][0] 和 dp[u][1] 时的方案数。 因为 dp[u][0] 只能从 dp[v][1] 转移，所以 cnt[u][0] 的状态转移是： cnt[u][0]=cnt[u][0]∗cnt[v][1]% mod 而 dp[u][1] 可以从 dp[v][0] 和 dp[v][1] 转移，所以需要根据 dp[v][0] 和 dp[v][1] 的大小确定 cnt[u][1] 是从 cnt[v][0] 转移还是从 cnt[v][1] 转移，或者两者均可 (dp[v][1]=dp[v][0]时) 。状态转移方程见代码。 时间复杂度： O(n) #include <stdio.h> #include <string.h> #include <algorithm> #include <math.h> using namespace std; typedef long long ll; const int MAX_N = 100020; const ll mod = 10007; int T, n, total, num; int head[MAX_N], dp[MAX_N][5]; ll cnt[MAX_N][5]; struct Edge { int v, next; } edge[MAX_N * 2]; void AddEdge(int u, int v) { edge[total].v = v; edge[total].next = head[u]; head[u] = total++; } void dfs(int u, int p) { dp[u][0] = 0, dp[u][1] = 1; cnt[u][0] = cnt[u][1] = 1; for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].v; if (v == p) continue; dfs(v, u); dp[u][0] += dp[v][1]; cnt[u][0] = cnt[u][0] * cnt[v][1] % mod; dp[u][1] += min(dp[v][1], dp[v][0]); if (dp[v][1] < dp[v][0]) { cnt[u][1] = cnt[u][1] * cnt[v][1] % mod; } else if (dp[v][1] > dp[v][0]) { cnt[u][1] = cnt[u][1] * cnt[v][0] % mod; } else { cnt[u][1] = cnt[u][1] * (cnt[v][1] + cnt[v][0]) % mod; } } } int main() { scanf("%d", &T); while (T--) { scanf("%d", &n); memset(head, -1, sizeof(head)); total = num = 0; for (int i = 1; i < n; ++i) { int u, v; scanf("%d%d", &u, &v); AddEdge(u, v); AddEdge(v, u); } dfs(1, 0); if (dp[1][0] < dp[1][1]) { printf("%d %lld\n", dp[1][0], cnt[1][0]); } else if (dp[1][0] > dp[1][1]) { printf("%d %lld\n", dp[1][1], cnt[1][1]); } else { printf("%d %lld\n", dp[1][0], (cnt[1][0] + cnt[1][1]) % mod); } } return 0; }