fork download
copy 
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<iostream>
  6. #include<fstream>
  7. #include<map>
  8. #include<ctime>
  9. #include<set>
  10. #include<queue>
  11. #include<cmath>
  12. #include<vector>
  13. #include<bitset>
  14. #include<functional>
  15. #define x first
  16. #define y second
  17. #define mp make_pair
  18. #define pb push_back
  19. #define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
  20. #define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
  21. using namespace std;
  22.  
  23. typedef long long LL;
  24. typedef double ld;
  25.  
  26.  
  27. const int MAX=600000+10;
  28.  
  29. int N;
  30. int begin[MAX],next[MAX],t[MAX],tot;
  31. int q[MAX],hash[MAX];
  32.  
  33. void add(int a,int b)
  34. {
  35. 	t[++tot]=b;
  36. 	next[tot]=begin[a];
  37. 	begin[a]=tot;
  38. }
  39.  
  40. int f[MAX];
  41.  
  42. int check(int k)
  43. {
  44. 	int i,j;
  45. 	for(i=N-1;i>=0;--i)
  46. 	{
  47. 		int u=q[i],sum=0;
  48. 		for(j=begin[u];j;j=next[j])
  49. 		{
  50. 			int v=t[j];
  51. 			if(hash[v]!=u)
  52. 				continue;
  53. 			++sum;
  54. 			sum+=f[v];
  55. 		}
  56. 		sum-=min(sum,k);
  57. 		f[u]=sum;
  58. 	}
  59. 	return f[1]==0;
  60. }
  61.  
  62. int main()
  63. {
  64. 	int i;
  65. 	scanf("%d",&N);
  66. 	REP(i,1,N-1)
  67. 	{
  68. 		int a,b;
  69. 		scanf("%d%d",&a,&b);
  70. 		add(a,b);
  71. 		add(b,a);
  72. 	}
  73. 	int head=0,end=0;
  74. 	q[end++]=1;
  75. 	hash[1]=-1;
  76. 	while(head<end)
  77. 	{
  78. 		int u=q[head++];
  79. 		for(i=begin[u];i;i=next[i])
  80. 		{
  81. 			int v=t[i];
  82. 			if(!hash[v])
  83. 			{
  84. 				q[end++]=v;
  85. 				hash[v]=u;
  86. 			}
  87. 		}
  88. 	}
  89. 	int left=0,right=N;
  90. 	while(left<right)
  91. 	{
  92. 		int mid=(left+right)/2;
  93. 		if(check(mid))
  94. 			right=mid;
  95. 		else left=mid+1;
  96. 	}
  97. 	printf("%d\n",left);
  98. 	return 0;
  99. }
  100.  
Success #stdin #stdout 0s 17408KB
comments (?)
stdin
copy 
13
1 2
1 3
2 4
2 5
3 6
3 7
2 8
3 9
2 10
3 11
2 12
3 13
stdout
copy 
4
https://ideone.com/85riw6
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!