Edge Groups
#树形结构 #组合数学 #树形dp
题目描述
Given an undirected connected graph of n n n vertices and n − 1 n-1 n−1 edges, where n n n is guaranteed to be odd. You want to divide all the n − 1 n-1 n−1 edges to n − 1 2 \frac{n-1}{2} 2n−1 groups under following constraints:
- There are exactly 2 edges in each group
- The 2 edges in the same group share a common vertex
Determine the number of valid dividing schemes modulo 998244353 998244353 998244353. Two schemes are considered different if there are 2 edges that are in the same group in one scheme but not in the same group in the other scheme.
输入格式
The first line contains one integer n ( 3 ≤ n ≤ 1 0 5 ) n\,(3\le n \le 10^5) n(3≤n≤105), denoting the number of vertices.
Following n − 1 n-1 n−1 lines each contains two integers u , v ( 1 ≤ u ≤ v ≤ n ) u,v\ (1 \leq u \leq v \leq n) u,v (1≤u≤v≤n), denoting that vertex u , v u,v u,v are undirectedly connected by an edge.
It is guaranteed that n n n is odd and that the given graph is connected.
输出格式
Output one line containing one integer, denoting the number of valid dividing schemes modulo 998244353 998244353 998244353.
样例 #1
样例输入 #1
7
1 2
1 3
1 7
4 7
5 7
6 7
样例输出 #1
3
解题思路
观察发现，如果子树的边的个数为奇数的时候，需要和选一条边和父节点的连边组合，剩下的边可以两两组合。
如下图：
其中， n n n条边两两组合的方案数共有 ∏ i = 1 i ≤ n f a c t i , i ∈ { o d d } \prod_{i=1}^{i\leq n}fact_i \ , i \in \{odd\} ∏i=1i≤nfacti ,i∈{odd} 即不大于 n n n的奇数的阶乘之积，可以通过数学归纳法证明，这里不多赘述。
因此，转移方程为：
f u = f u ∏ v ∏ i = 1 i ≤ n f v f a c t i ( v ∈ c h i l d u , i ∈ { o d d } ) f_u = f_u\prod_v \prod_{i=1}^{i \leq n} f_v fact_i \ ( v \in child_u,i \in \{ odd\}) fu=fuv∏i=1∏i≤nfvfacti (v∈childu,i∈{odd})
代码
const int N = 1e6 + 7;
vector<int> e[N];
int f[N], sz[N];
void dfs(int u, int fa){
f[u] = 1;
for (auto &v : e[u]) {
if (v == fa) continue;
dfs(v, u);
if (sz[v] % 2 == 0) sz[u]++;
f[u] = f[u] * f[v] % mod;
}
if (sz[u] >= 2) {
for (int i = 1; i <= sz[u]; i += 2) {
f[u] = f[u] * i % mod;
}
}
}
void solve()
{
int n;
cin >> n;
for (int i = 1; i <= n - 1; i++) {
int u, v;
cin >> u >> v;
e[u].push_back(v), e[v].push_back(u);
}
dfs(1, -1);
cout << f[1]<< endl;
}
signed main() {
ios::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);
int t = 1;
//cin >> t;
while (t--) {
solve();
}
};