fork download
copy 
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <ctime>
  6. #include <algorithm>
  7. #include <iostream>
  8. #include <fstream>
  9. #include <vector>
  10. #include <queue>
  11. #include <deque>
  12. #include <map>
  13. #include <set>
  14. #include <bitset>
  15. #include <complex>
  16. #include <string>
  17. #define REP(i,j) for(int i=1;i<=j;++i)
  18. #define REPI(i,j,k) for(int i=j;i<=k;++i)
  19. #define REPD(i,j) for(int i=j;0<i;--i)
  20. #define CLR(s) memset(s,0,sizeof s)
  21. #define SET(s,v) memset(s,v,sizeof s)
  22. #define mp make_pair
  23. #define pb push_back
  24. #define x first
  25. #define y second
  26. using namespace std;
  27. string FILE_NAME = "meat";
  28. typedef long long LL;
  29. typedef double DB;
  30. const int INF = 0x3f3f3f3f;
  31.  
  32. const int maxn = 500000 + 500;
  33.  
  34. int fa[maxn],son[maxn],n;
  35. DB A[maxn],F[maxn];
  36. struct Edge
  37. {
  38. 	int head[maxn],next[maxn],to[maxn];
  39. 	int edge;
  40. 	void init()
  41. 	{
  42. 		edge=0;
  43. 		SET(head,-1);
  44. 	}
  45. 	void addedge(int a,int b)
  46. 	{
  47. 		next[edge]=head[a];
  48. 		to[edge]=b;
  49. 		head[a]=edge++;
  50. 	}
  51. }E;
  52.  
  53. int cnt;
  54.  
  55. int dcmp(DB d)
  56. {
  57. 	if(fabs(d)<1e-8)
  58. 		return 0;
  59. 	return d<0?-1:1;
  60. }
  61.  
  62. DB add[maxn];
  63.  
  64. void dfs(int t)
  65. {
  66. 	if(son[t]==0) return ;
  67. 	for(int i=E.head[t];i!=-1;i=E.next[i])
  68. 	{
  69. 		F[E.to[i]]=F[t]+add[t];
  70. 		dfs(E.to[i]);
  71. 	}
  72. }
  73.  
  74. bool cmp(DB a,DB b)
  75. {
  76. 	return dcmp(a-b)<0;
  77. }
  78.  
  79. int main()
  80. {
  81.  
  82. 	scanf("%d",&n);
  83. 	E.init();
  84. 	for(int i=1;i<=n;++i)
  85. 	{
  86. 		scanf("%lf",&A[i]);
  87. 	}
  88. 	for(int i=1;i<n;++i)
  89. 	{
  90. 		int a,b;
  91. 		scanf("%d%d",&a,&b);
  92. 		fa[b]=a;
  93. 		++son[a];
  94. 		E.addedge(a,b);
  95. 	}
  96.  
  97. 	for(int i=1;i<=n;++i)
  98. 	{
  99. 		add[i]=log(son[i]);
  100. 	}
  101.  
  102. 	F[1]=0;
  103. 	dfs(1);
  104. 	for(int i=1;i<=n;++i)
  105. 	{
  106. 		F[i]+=log(A[i]);
  107. 	}
  108.  
  109. 	sort(F+1,F+n+1,cmp);
  110. 	int ans=0;
  111. 	for(int i=1;i<=n;++i)
  112. 	{
  113. 		int cnt=1;
  114. 		while(dcmp(F[i]-F[i+1])==0 && i+1<=n)
  115. 		{
  116. 			++cnt;
  117. 			++i;
  118. 		}
  119. 		if(cnt>ans)
  120. 			ans=cnt;
  121. 	}
  122. 	printf("%d\n",n-ans);
  123. 	return 0;
  124. }
  125.  
Success #stdin #stdout 0s 24992KB
comments (?)
stdin
copy 
10
3
4
6
3
2
5
3
1
1
4
1 2
1 3
2 4
3 5
4 6
5 7
6 8
6 9
6 10
stdout
copy 
6
https://ideone.com/ttstZl
HNOI2014 米特运输 meat
language:
C++ (gcc 8.3)
created:
10 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!