fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <string>
  4. #include <sstream> 
  5. #include <vector>
  6. #include <set>
  7. #include <map>
  8. #include <queue>
  9. #include <stack>
  10. #include <cmath>
  11. #include <algorithm>
  12. #include <cstring>
  13. #include <ctime>
  14. #include <cassert>
  15. #include <unordered_map>
  16.  
  17. using namespace std;
  18. #define pb push_back
  19. #define mp make_pair
  20. #define pii pair<int,int>
  21. #define vi vector<int>
  22. #define vpii vector<pii>
  23. #define SZ(x) ((int)(x.size()))
  24. #define fi first
  25. #define se second
  26. #define FOR(i,n) for(int (i)=0;(i)<(n);++(i))
  27. #define FORI(i,n) for(int (i)=1;(i)<=(n);++(i))
  28. #define IN(x,y) ((y).find((x))!=(y).end())
  29. #define ALL(t) t.begin(),t.end()
  30. #define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
  31. #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
  32. #define REPD(i,a,b) for(int (i)=(a); (i)>=(b);--i)
  33. #define REMAX(a,b) (a)=max((a),(b));
  34. #define REMIN(a,b) (a)=min((a),(b));
  35.  
  36.  
  37. const int N = 5e5;
  38.  
  39. vi g[N];
  40.  
  41. unordered_map<int,int> l_sub[N] , l_path[N];
  42. int sub_max[N],m_path[N];
  43. vector<pii > ans;
  44.  
  45. void dfs1(int v, int p)
  46. {
  47. 	int n = g[v].size();
  48. 	vector<int> child;
  49. 	for(int i = 0;i<n; i++)
  50. 	{
  51. 		int c = g[v][i];
  52. 		if(c==p) continue;
  53. 		dfs1(c,v);
  54. 		child.pb(c);
  55. 		m_path[v]  = max( m_path[v], m_path[c] + 1);
  56. 	}
  57.  
  58. 	int  tot = 0;
  59. 	for(int i = 0;i<child.size();i++)
  60. 	{
  61. 		sub_max[v] = max(sub_max[child[i]],sub_max[v]);
  62. 		tot += m_path[child[i]] + 1;
  63. 		sub_max[v] = max(tot,sub_max[v]);
  64. 	}
  65.  
  66. 	if(child.size()==2)
  67. 	{
  68.  
  69. 		l_path[v][child[0]] = m_path[child[1]] + 1;
  70. 		l_path[v][child[1]] = m_path[child[0]] + 1;
  71.  
  72. 		l_sub[v][child[0]] = max( sub_max[child[1]], m_path[child[1]] + 1);
  73. 		l_sub[v][child[1]] = max( sub_max[child[0]], m_path[child[0]] + 1);
  74.  
  75. 	}
  76.  
  77. }
  78.  
  79. void dfs2(int v, int p, int lup, int bup, int k)
  80. {
  81. 	if(v!=1)
  82. 	{
  83. 		lup = lup + 1;
  84. 		bup = max(bup,lup);
  85. 	}
  86. 	int n = g[v].size(); 
  87. 	for(int i = 0; i<n; i++)
  88. 	{
  89. 		int c = g[v][i];
  90. 		if(c==p) continue;
  91. 		int d1 = sub_max[c];
  92. 		int d2 = max(l_sub[v][c], lup + l_path[v][c] );
  93.  
  94. 		if(abs(d1-d2)<k)
  95. 		{
  96. 			//cout<<"Found "<<v<<"->"<<c<<" dia of child = "<<d1<<" dia of upper = "<<d2<<" lup = "<<lup<<" l_sub[v][c] = "<<l_sub[v][c]<<endl;
  97. 			cout<<"Found "<<v<<"->"<<c<<" dia of child = "<<d1<<" dia of upper = "<<d2<<endl;
  98. 		}
  99.  
  100. 		//bup = max( bup, d2 );
  101. 		//lup = max( lup, l_path[v][c] );
  102. 		dfs2(c,v,max(lup,l_path[v][c]),max(bup,d2),k); 
  103. 	}
  104. }
  105.  
  106.  
  107.  
  108. int main()
  109. {
  110. 	int n,m,u,v,k;
  111. 	cin>>n>>k;
  112. 	for(int i=0;i<n-1;i++)
  113. 	{
  114. 		cin>>u>>v;
  115. 		g[u].pb(v);
  116. 		g[v].pb(u);
  117. 	}
  118.  
  119. 	dfs1(1,0);
  120. 	dfs2(1,0,0,0,k);
  121.  
  122. 	// for(int i =1;i<=n;i++)
  123. 	// {
  124. 	// 	cout<<i<<" sub_max = "<<sub_max[i]<<"   m_path = "<<m_path[i]<<endl;
  125. 	// }
  126.  
  127.  
  128. 	return 0;
  129. }
Success #stdin #stdout 0.02s 85568KB
comments (?)
stdin
copy 
11 7
1 2
1 3
2 4 
2 5
4 8
4 9
3 6
3 7
7 10 
7 11
stdout
copy 
Found 1->2 dia of child = 3 dia of upper = 3
Found 2->4 dia of child = 2 dia of upper = 5
Found 4->8 dia of child = 0 dia of upper = 6
Found 4->9 dia of child = 0 dia of upper = 6
Found 2->5 dia of child = 0 dia of upper = 6
Found 1->3 dia of child = 3 dia of upper = 3
Found 3->6 dia of child = 0 dia of upper = 6
Found 3->7 dia of child = 2 dia of upper = 5
Found 7->10 dia of child = 0 dia of upper = 6
Found 7->11 dia of child = 0 dia of upper = 6
https://ideone.com/LypbPw
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!