【组合计数 or 树DP】2021 icpc 上海 G

- 日理万妓 2024-03-26 22:21 115阅读 0赞

[Problem - G - Codeforces][]

题意：

![860dc155a48e491b99a13e7028a0abd9.png][]

![eed639146c6a47de94bcd2a8c0564627.png][]![de9ac8a004ac4bf4ae7704ec57990296.png][]

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e6+10;
    const int mxv=1e6+10;
    const int mod=998244353;
    
    vector<int> G[mxn];
    
    int N,u,v;
    int ans=1;
    int sz[mxn];
    
    void dfs(int u,int fa){
    	int cnt=0;
    	sz[u]=1;
    	for(auto v:G[u]){
    		if(v==fa) continue;
    		dfs(v,u);
    		sz[u]+=sz[v];
    		if(sz[v]&1) cnt++;
    	}
    	if(cnt&1) cnt++;
    	for(int i=cnt-1;i>=0;i-=2){
    		ans=ans*i%mod;
    	}
    }
    void solve(){
    	cin>>N;
    	for(int i=1;i<=N-1;i++){
    		cin>>u>>v;
    		G[u].push_back(v);
    		G[v].push_back(u);
    	}
    	dfs(1,0);
    	cout<<ans%mod<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[Problem - G - Codeforces]: https://codeforces.com/gym/103446/problem/G
[860dc155a48e491b99a13e7028a0abd9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/0c327c9233c34c09b0da4df62993c335.png
[eed639146c6a47de94bcd2a8c0564627.png]: https://img-blog.csdnimg.cn/eed639146c6a47de94bcd2a8c0564627.png
[de9ac8a004ac4bf4ae7704ec57990296.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/d0c9fb0a3b294f01a566d1bd2c2c37a1.png

发表评论取消回复

表情：

评论列表（有 0 条评论，115人围观）

还没有评论，来说两句吧...

相关阅读

相关【组合计数 or 树DP】2021 icpc 上海 G

[Problem - G - Codeforces][] 题意： ![860dc155a48e491b99a13e7028a0abd9.png][] ![eed63914

- 日理万妓/ 2024年03月26日 22:21/ 0 赞/ 116 阅读

相关【暴力DP】2021 icpc上海 I

[Problem - I - Codeforces][] 题意： ![01d23059f1114440bc2d82d7f8bf21f3.png][] ![83f6684a

谁践踏了优雅/ 2024年03月26日 22:21/ 0 赞/ 105 阅读

相关【树DP】2021ICPC南京 H

[Problem - H - Codeforces][] 题意： ![2b473d7ad29d4bffbd1d05014beff24f.png][] 思路：这题应该

待我称王封你为后i/ 2024年03月24日 23:50/ 0 赞/ 122 阅读

相关【枚举边+MST+组合计数】CF1857G

[Problem - 1857G - Codeforces][] 题意： ![4a0694b3491d4b64a4432fb12c43d801.png][] ![fbe

痛定思痛。/ 2024年03月23日 23:18/ 0 赞/ 130 阅读

相关【树上乘法原理】ICPC Shanghai 2021 G, Edge Groups

[http://oj.daimayuan.top/course/8/problem/400][http_oj.daimayuan.top_course_8_problem_40

àì夳堔傛蜴生んèń/ 2024年03月22日 21:50/ 0 赞/ 102 阅读

相关【期望+状压DP】 2021 CCPC G

[Problem - G - Codeforces][] 题意： ![dca96a9702b54c1590f9e441a4f72d6e.png][] ![5d06c9b7

红太狼/ 2024年03月01日 07:47/ 0 赞/ 87 阅读

相关【2021ICPC沈阳】EFBJHL

不知道为什么感觉以前的场要比现在的简单一点，虽然这场VP虽然题数到了但是还是差点罚时.... 现在的有些场感觉连签到都要签半天，比如前几天的ICPC西安和CCPC桂林，看了下

川长思鸟来/ 2024年02月20日 10:47/ 0 赞/ 88 阅读

相关 2019 ICPC 上海网络赛

摸了一整场的鱼，签了个到，做了个FFT还忘记初始化赛后才发现 B.00:16:52 solved by hl 很显然前缀和搞搞就行了，但是卡O(N),要O(M) !

深藏阁楼爱情的钟/ 2023年10月10日 07:51/ 0 赞/ 115 阅读

相关 2019ICPC上海网络赛A 边分治+线段树

题目：给定一棵树，带边权。现在有2种操作： 1.修改第i条边的权值。 2.询问u到其他一个任意点的最大距离是多少。解法：边分治+线段树首先我们将所有的点修

女爷i/ 2023年06月04日 11:52/ 0 赞/ 22 阅读

相关计数（dp

描述：计算从1到n中，每个数字（0到9）出现的次数其中sum[j]和dp[i]表示：数字i中 j 的个数；比如sum[1]和dp[5]就可以表示：5中1的

梦里梦外;/ 2022年06月18日 00:29/ 0 赞/ 241 阅读