自己做服务器的网站,作品提示优化要删吗,免费网站空间怎么做网站,常德网站设计http://oj.daimayuan.top/course/8/problem/400
题意#xff1a; 思路#xff1a;
求方案数#xff0c;考虑组合数学
手摸一下样例发现#xff0c;对于一棵子树#xff0c;若边数为偶数#xff0c;那么可以内部匹配#xff0c;但是如果边数为奇数#xff0c;那么就一…http://oj.daimayuan.top/course/8/problem/400
题意 思路
求方案数考虑组合数学
手摸一下样例发现对于一棵子树若边数为偶数那么可以内部匹配但是如果边数为奇数那么就一定需要u和fa那条边和子树的边匹配
考虑乘法原理 将多出来的边进行匹配
如果边数还为奇数那么就和u和fa这条边匹配
若多出来K条边由乘法原理知道方案数为(K-1)*(K-3)*....
Code
#include bits/stdc.h#define int long longusing namespace std;const int mxn1e610;
const int mxv1e610;
const int mod998244353;vectorint G[mxn];int N,u,v;
int ans1;
int sz[mxn];void dfs(int u,int fa){int cnt0;sz[u]1;for(auto v:G[u]){if(vfa) continue;dfs(v,u);sz[u]sz[v];if(sz[v]1) cnt;}if(cnt1) cnt;for(int icnt-1;i0;i-2){ansans*i%mod;}
}
void solve(){cinN;for(int i1;iN-1;i){cinuv;G[u].push_back(v);G[v].push_back(u);}dfs(1,0);coutans%mod\n;
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __1;//cin__;while(__--)solve();return 0;
}
