fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. const int N = 2e5+5, MOD = 998244353;
  6.  
  7. int n;
  8. vector<int> a[N];
  9. int b[N];
  10. long long f[N];
  11.  
  12. int dfs(int x,int par) {
  13. 	int total = 1;
  14. 	for(int ch:a[x]) if(ch != par) total += dfs(ch,x);
  15. 	b[x] = total;
  16. 	return b[x];
  17. }
  18.  
  19. void pre() {
  20. 	f[0] = 1;
  21. 	for(int i=1;i<N;i++) {
  22. 		f[i] = (f[i-1]*i) % MOD;
  23. 	}
  24. }
  25.  
  26. int go(int x,int par,int bubble) {
  27. 	int children = 0;
  28. 	for(int ch : a[x]) if(ch != par) children++;
  29. 	long long ans = f[children];
  30. 	for(int ch : a[x]) if(ch != par) {
  31. 		ans = (ans * go(ch,x,b[ch])) % MOD;
  32. 	}
  33. 	ans = (ans * bubble) % MOD;
  34. 	return (ans % MOD);
  35. }
  36.  
  37. int main() {
  38. 	cin >> n;
  39. 	for(int i=1;i<n;i++) {
  40. 		int x,y; cin >> x >> y;
  41. 		a[x].push_back(y);
  42. 		a[y].push_back(x);
  43. 	}
  44. 	dfs(1,-1);
  45. 	pre();
  46. 	int ans = go(1,-1,n) % MOD;
  47. 	cout << ans;
  48. }
Success #stdin #stdout 0s 22272KB
comments (?)
stdin
copy 
2
1 2
stdout
copy 
2
https://ideone.com/u6ufBL
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!