算法
(树上dfs、01背包) $O(NR)$
如果你搜一下每条边经过的次数,你会得到这样的问题:”有多少种方法可以从 $C_1, C_2, \cdots, C_n$ 中选一些点使得红色边经过的次数为 $X$”。
记 $R$ 为经过的红色边的边数,$B$ 为经过的蓝色边的边数,$S$ 为经过的所有边的边数
我们可以得到如下方程组
$ \begin{cases} R - B = K \\\ R + B = S \end{cases} $
解得, $R = \frac{K + S}{2}$
对于每条边经过的次数,我们可以看成是价值,然后选择树上这 $N - 1$ 边中的一些边染成红色,使得总价值为 $R$
这显然是经典的 01背包
问题
最后注意需要特判 $K + S$ 是否合理
C++ 代码
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using mint = modint998244353;
struct Edge {
int to, id;
Edge() {}
Edge(int to, int id): to(to), id(id) {}
};
int main() {
int n, m, k;
cin >> n >> m >> k;
vector<int> A(m);
rep(i, m) cin >> A[i];
vector<vector<Edge>> g(n);
rep(i, n - 1) {
int a, b;
cin >> a >> b;
--a; --b;
g[a].emplace_back(b, i);
g[b].emplace_back(a, i);
}
vector<int> c(n - 1);
rep(i, m - 1) {
int sv = A[i] - 1, tv = A[i + 1] - 1;
auto dfs = [&](auto& f, int v, int p = -1) -> bool {
if (v == tv) return true;
for (auto e : g[v]) {
if (e.to == p) continue;
if (f(f, e.to, v)) {
c[e.id]++;
return true;
}
}
return false;
};
dfs(dfs, sv);
}
int s = 0;
rep(i, n - 1) s += c[i];
int r2 = k + s;
if (r2 < 0 or r2 > s * 2 or r2 % 2 == 1) {
puts("0");
return 0;
}
int r = r2 / 2;
vector<mint> dp(r + 1);
dp[0] = 1;
for (int x : c) {
for (int i = r - x; i >= 0; --i) dp[i + x] += dp[i];
}
cout << dp[r].val() << '\n';
return 0;
}