fork download
copy 
  1. #include <bits/stdc++.h>
  2. const int N = 2e5;
  3. #define ll long long
  4. using namespace std;
  5.  
  6. int n, k;
  7. vector<int> v[N+3];
  8. int cnt[N+3], xxx = 0;
  9. bool check[N+3];
  10. int tree[N+3];
  11. ll ans = 0;
  12.  
  13. void dfs(int t, int par) {
  14.     tree[t] = 1;
  15. 	for (int res : v[t]){
  16.         if(res == par)continue;
  17. 		if (!check[res]){
  18.             dfs(res, t);
  19. 			tree[t] += tree[res];
  20. 		}
  21.     }
  22.  
  23. }
  24.  
  25. int centroid1(int t, int par, int n) {
  26. 	for (int res : v[t]){
  27.         if(res == par)continue;
  28. 		if (!check[res] and tree[res] >= n/2){
  29. 			return centroid1(res, t, n);
  30. 		}
  31. 	}
  32. 	return t;
  33. }
  34.  
  35. void dfs2(int t, int par, bool ok, int res) {
  36. 	if(res > k)return;
  37. 	xxx = max(xxx, res);
  38. 	if(ok)cnt[res]++;
  39. 	else ans += cnt[k - res];
  40. 	for (int x : v[t]){
  41.         if(x == par)continue;
  42. 		if (!check[x])dfs2(x, t, ok, res+1);
  43. 	}
  44. }
  45.  
  46. void centroid2(int t){
  47.     dfs(t, 0);
  48. 	int res = centroid1(t, 0, tree[t]);
  49. 	check[res] = true;
  50. 	xxx = 0;
  51. 	cnt[0] = 1;
  52. 	for (int x : v[res]){
  53. 		if (!check[x]) {
  54. 			dfs2(x, res, false, 1);
  55. 			dfs2(x, res, true, 1);
  56. 		}
  57. 	}
  58. 	for(int i=1;i<=xxx;i++)cnt[i] = 0;
  59. 	for (int x : v[res]){
  60. 		if (!check[x])centroid2(x);
  61. 	}
  62. }
  63.  
  64. int main() {
  65. 	ios_base::sync_with_stdio(0);
  66. 	cin.tie(0);
  67. 	cin>>n>>k;
  68. 	for (int i=1;i<=n-1;i++){
  69. 		int x, y;
  70. 		cin>>x>>y;
  71. 		v[x].push_back(y);
  72. 		v[y].push_back(x);
  73. 	}
  74. 	centroid2(1);
  75. 	cout<<ans<<"\n";
  76. 	return 0;
  77. }
  78.  
Success #stdin #stdout 0.01s 8840KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/RopyY2
language:
C++14 (gcc 8.3)
created:
1 day 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!