fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int n, m;
  5. vector <int> G[1000005];
  6. int is[1000005];
  7.  
  8.  
  9. int cnt;
  10.  
  11. int dfs(int v, int k, int f) {
  12.  
  13. 	int result = 0;
  14.  
  15. 	for(int i = 0; i < G[v].size(); i++) {
  16. 		int &u = G[v][i];
  17. 		if(u == f) continue;
  18. 		int x = dfs(u,k,v);
  19.  		cerr << "vertex " << u << " = " << x << endl;
  20. 		if(x == 0) continue;
  21. 		if(result == 0) {
  22. 			result = x;
  23. 		} else if(x < 0) {
  24. 			if(result > 0) {
  25. 				if(-x-1 >= result) {
  26. 					result = x;
  27. 				}
  28. 			} else {
  29. 				result = min(result,x);
  30. 			}
  31. 		} else {
  32. 			if(result < 0) {
  33. 				if(x > -result-1) {
  34. 					result = x;
  35. 				}
  36. 			} else {
  37. 				result = max(result,x);
  38. 			}
  39. 		}
  40. 	}
  41.  
  42. 	if(result != 0) {
  43. 		if(result == k) {
  44. 			cnt++;
  45. 			return -k;
  46. 		} else {
  47. 			return result+1;
  48. 		}
  49. 	} else {
  50. 		if(k == 0 && is[v]) {
  51. 			cnt++;
  52. 			return 0;
  53. 		}
  54. 		return is[v];
  55. 	}
  56. }
  57.  
  58. int main() {
  59. 	scanf("%d %d",&n,&m);
  60. 	for(int i = 0; i < n; i++)
  61. 		scanf("%d",&is[i+1]);
  62. 	for(int i = 0; i < n-1; i++) {
  63. 		int a, b;
  64. 		scanf("%d %d",&a,&b);
  65. 		G[a].push_back(b);
  66. 		G[b].push_back(a);
  67. 	}
  68.  
  69. 	int s = 0;
  70. 	int t = n;
  71. 	cerr << "For 2" << endl;
  72. 	dfs(1, 2, -1);
  73.  
  74. 	while(s < t) {
  75. 		cnt = 0;
  76. 		int mid = (s+t)/2;
  77.  		cerr << "Binary search " << mid << endl;
  78. 		int x = dfs(1,mid,-1);
  79.  
  80. 		if(x > 0) cnt++;
  81. // 		cerr << "Result " << " = " << cnt << endl;
  82. 		if(cnt <= m) {
  83. 			t = mid;
  84. 		} else {
  85. 			s = mid+1;
  86. 		}
  87.  
  88.  
  89. 	}
  90. 	printf("%d\n",s);
  91.  
  92. }
Success #stdin #stdout #stderr 0s 43408KB
comments (?)
stdin
copy 
12 10
1 1 1 1 1 1 1 1 1 1 1 1
1 2
2 3
3 4
4 5
5 6
6 7
6 11
6 8
8 9
8 10
9 12
stdout
copy 
1
stderr
copy 
For 2
vertex 7 = 1
vertex 11 = 1
vertex 12 = 1
vertex 9 = 2
vertex 10 = 1
vertex 8 = -2
vertex 6 = -1
vertex 5 = 0
vertex 4 = 1
vertex 3 = 2
vertex 2 = -2
Binary search 6
vertex 7 = 1
vertex 11 = 1
vertex 12 = 1
vertex 9 = 2
vertex 10 = 1
vertex 8 = 3
vertex 6 = 4
vertex 5 = 5
vertex 4 = 6
vertex 3 = -6
vertex 2 = -5
Binary search 3
vertex 7 = 1
vertex 11 = 1
vertex 12 = 1
vertex 9 = 2
vertex 10 = 1
vertex 8 = 3
vertex 6 = -3
vertex 5 = -2
vertex 4 = -1
vertex 3 = 0
vertex 2 = 1
Binary search 1
vertex 7 = 1
vertex 11 = 1
vertex 12 = 1
vertex 9 = -1
vertex 10 = 1
vertex 8 = -1
vertex 6 = -1
vertex 5 = 0
vertex 4 = 1
vertex 3 = -1
vertex 2 = 0
Binary search 0
vertex 7 = 0
vertex 11 = 0
vertex 12 = 0
vertex 9 = 0
vertex 10 = 0
vertex 8 = 0
vertex 6 = 0
vertex 5 = 0
vertex 4 = 0
vertex 3 = 0
vertex 2 = 0
https://ideone.com/ideP9v
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!