[数据结构与算法]Edge Groups 思维 树形dp

Given an undirected connected graph of?nn?vertices and?n?1n?1?edges, where?nn?is guaranteed to be odd. You want to divide all the?n?1n?1?edges to?n?12n?12?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?998244353998244353. 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.

Input

The first line contains one integer?n(3≤n≤105)n(3≤n≤105), denoting the number of vertices.

Following?n?1n?1?lines each contains two integers?u,v(1≤u<v≤n)u,v(1≤u<v≤n), denoting that vertex?u,vu,v?are undirectedly connected by an edge.

It is guaranteed that?nn?is odd and that the given graph is connected.

Output

Output one line containing one integer, denoting the number of valid dividing schemes modulo?998244353998244353.

Example

input

Copy

7
1 2
1 3
1 7
4 7
5 7
6 7

output

Copy

3

Note

The 3 schemes are:

• The 3 edge groups are?{1?2,1?3},{1?7,4?7},{5?7,6?7}{1?2,1?3},{1?7,4?7},{5?7,6?7}
• The 3 edge groups are?{1?2,1?3},{1?7,5?7},{4?7,6?7}{1?2,1?3},{1?7,5?7},{4?7,6?7}
• The 3 edge groups are?{1?2,1?3},{1?7,6?7},{4?7,5?7}{1?2,1?3},{1?7,6?7},{4?7,5?7}

拿这个图来分析

对于2这个结点 只能24 和 25? 组成一组 对于3这个结点 因为73 和 79 组成一组所以3结点是无法用37这条边的 计算3的贡献的时候要忽略37这条边

计算贡献的方法：对于一个结点如果它与它子结点的有效边是偶数的话（上图2，3结点都是这种情况）假设有效边数是n 对这n条边进行全排列方案数是n！因为每组里面的边是没有顺序的 所以除以2^(n/2) 然后又因为每组是没有顺序的所以除以(n/2)! 然后得到(n-1)!! 两个!表示所有奇数的乘积

当然还要乘上每一个子结点的贡献

如果是奇数的话 就是(n-2)!! * n 也就是 n!!

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100010,MAX = 0x3f3f3f3f,mod = 998244353;
ll dp[MAXN];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int n,t1,t2;
	cin >> n;
	vector<int> v[n+1];
	for(int i = 1;i < n; i++){
		cin >> t1 >> t2;
		v[t1].push_back(t2);
		v[t2].push_back(t1);
	} 
	function<int(int,int)> dfs = [&] (int now,int fath){
		dp[now] = 1;
		int cnt = 0;
		for(int x : v[now]){
			if(x == fath) continue;
			if(!dfs(x,now)) cnt++;
			dp[now] = (dp[now]*dp[x])%mod;
		}
		for(int i = 1;i <= cnt; i += 2) dp[now] = (dp[now]*i)%mod;
		return cnt&1;
	};
	dfs(1,0);
	cout << dp[1];
	return 0;
}

?