VOCV - Con-Junctions
题目大意：
一个 \(n\) 个节点的树，需要在某一些节点放置灯最终点亮所有边。
当一个节点上放置灯后，与它相连的所有边都被点亮。
试求最少放置的灯的数量与放灯最少时的方案数。方案数膜 10007 输出。
思路：
我们可以想到树形 \(dp\) .
设 \(f[i][0/1]\) 表示 \(i\) 节点是否放置灯的以 \(i\) 为根节点的树的最少放置灯数。
那么可以想到转移：
\[f[i][1] += \min(f[to][1], f[to][0]), to \in son_i \]\[f[i][0] += f[to][1], to \in son_i \]同理我们在转移 \(f\) 时更新 \(ans\)（存储最少时的方案数）
如果 \(f[to][0] < f[to][1]\) ，\(ans[i][1] = ans[i][1] * ans[to][0]\)
如果 \(f[to][0] > f[to][1]\)， \(ans[i][1] = ans[i][1] * ans[to][1]\)
如果 \(f[to][0] == f[to][1]\) ，\(ans[i][1] = (ans[to][0] + ans[to][1]) * ans[i][1]\)
\(ans[i][0] = ans[i][0] * ans[to][1]\)
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int Mod = 10007;
int t, n, cnt, head[N], f[N][5];
long long ans[N][5];
struct Edge {
int to, next;
}e[N << 1];
inline int read() {
int x = 0, f = 1;
char c = getchar();
while (!isdigit(c)) {
if (c == '-') f = -1;
c = getchar();
}
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
return x * f;
}
inline void add(int x, int y) {
e[++cnt].to = y;
e[cnt].next = head[x];
head[x] = cnt;
}
inline void dfs(int x, int fa) {
f[x][1] = 1;
f[x][0] = 0;
ans[x][1] = ans[x][0] = 1;
int to;
for (int i = head[x]; i ; i = e[i].next) {
to = e[i].to;
if (to == fa) continue;
dfs(to, x);
// f[x][1] += min(f[to][1], f[to][0]);
// f[x][0] += f[to][1];
if (f[to][1] < f[to][0]) {
f[x][1] += f[to][1];
ans[x][1] = (ans[x][1] * ans[to][1]) % Mod;
}
else if (f[to][0] < f[to][1]) {
f[x][1] += f[to][0];
ans[x][1] = (ans[x][1] * ans[to][0]) % Mod;
}
else if (f[to][0] == f[to][1]) {
f[x][1] += f[to][1];
ans[x][1] = ans[x][1] * (ans[to][1] + ans[to][0]) % Mod;
}
f[x][0] += f[to][1];
ans[x][0] = ans[x][0] * ans[to][1] % Mod;
}
}
signed main() {
t = read();
while (t--) {
cnt = 0;
memset(head, 0, sizeof (head));
memset(f, 0, sizeof (f));
n = read();
int x, y;
for (int i = 1; i <= n - 1; ++i) {
x = read(), y = read();
add(x, y);
add(y, x);
}
dfs(1, 0);
if (f[1][1] < f[1][0]) printf("%d %lld\n", f[1][1], ans[1][1]);
else if (f[1][1] > f[1][0]) printf("%d %lld\n", f[1][0], ans[1][0]);
else if (f[1][1] == f[1][0]) printf("%d %lld\n", f[1][0], (ans[1][0] + ans[1][1]) % Mod);
}
return 0;
}