fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #define mod 10007
  3. using namespace std;
  4. int t, n, u, v, dp1[110000], dp2[110000], ways1[110000], ways2[110000];
  5. vector< vector<int> > graph(110000);
  6.  
  7. void solve(int index, int par)
  8. {
  9. 	dp1[index] = 1;
  10. 	dp2[index] = 0;
  11. 	ways1[index] = ways2[index] = 1;
  12. 	for (int i = 0; i < graph[index].size(); i++)
  13. 	{
  14. 		int node = graph[index][i];
  15. 		if (node == par)
  16. 			continue;
  17. 		solve(node, index);
  18. 		if (dp1[node] == dp2[node])
  19. 		{
  20. 			dp1[index] += dp1[node];
  21. 			dp2[index] += dp1[node];
  22. 			ways1[index] *= (ways1[node]+ways2[node]);
  23. 			ways2[index] *= ways1[node];
  24. 			ways1[index] %= mod;
  25. 			ways2[index] %= mod;
  26. 		}
  27. 		else
  28. 		{
  29. 			dp1[index] += min(dp1[node], dp2[node]);
  30. 			dp2[index] += dp1[node];
  31. 			ways1[index] *= (min(dp1[node], dp2[node]) == dp1[node] ? ways1[node] : ways2[node]);
  32. 			ways2[index] *= ways1[node];
  33. 			ways1[index] %= mod;
  34. 			ways2[index] %= mod;
  35. 		}
  36. 	}
  37. }
  38.  
  39. int main()
  40. {
  41. 	ios::sync_with_stdio(false); cin.tie(0);
  42. 	cin>>t;
  43. 	for (int i = 0; i < t; i++)
  44. 	{
  45. 		cin>>n;
  46. 		for (int j = 0; j <= n; j++)
  47. 		{
  48. 			dp1[j] = dp2[j] = n+1;
  49. 			graph[j].clear();
  50. 			ways1[j] = ways2[j] = 1;
  51. 		}
  52. 		for (int j = 0; j < n-1; j++)
  53. 		{
  54. 			cin>>u>>v;
  55. 			graph[u].push_back(v);
  56. 			graph[v].push_back(u);
  57. 		}
  58. 		solve(1, -1);
  59. 		if (dp1[1] == dp2[1])
  60. 		{
  61. 			cout<<dp1[1]<<" "<<(ways1[1]+ways2[1])%mod<<"\n";
  62. 		}
  63. 		else if (dp1[1] < dp2[1])
  64. 		{
  65. 			cout<<dp1[1]<<" "<<ways1[1]<<"\n";
  66. 		}
  67. 		else
  68. 		{
  69. 			cout<<dp2[1]<<" "<<ways2[1]<<"\n";
  70. 		}
  71. 	}
  72. }
Success #stdin #stdout 0s 5216KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/uPh7Ju
language:
C++14 (gcc 8.3)
created:
6 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!