fork download
copy 
  1. // TREEISO
  2. #include<bits/stdc++.h>
  3. #define int long long
  4. #define rep(i,a,b) for(int i(a);i<=(b);++i)
  5. #define req(i,a,b) for(int i(a);i>=(b);--i)
  6. #define sort stable_sort
  7. using namespace std;
  8. char buf[1<<23],*p1=buf,*p2=buf;
  9. #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
  10. template<typename TP> inline TP read(TP &num)
  11. {
  12. 	TP x=0;
  13. 	int f=0;
  14. 	char ch=getchar();
  15. 	while(ch<48||ch>57) f|=ch=='-',ch=getchar();
  16. 	while(48<=ch&&ch<=57) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
  17. 	return num=f?-x:x;
  18. }
  19. template<typename ...Args> inline void read(Args &...args)
  20. {
  21. 	(read(args),...);
  22. }
  23. template<typename TP> inline void write(TP x)
  24. {
  25. 	(x<0)?(putchar('-'),x=-x):0;
  26. 	(x>9)?(write(x/10),0):0;
  27. 	putchar((x%10)^48);
  28. }
  29. template<typename TP> inline void writeln(TP x)
  30. {
  31. 	write<TP>(x);
  32. 	puts("");
  33. }
  34. int T,m,n[3];
  35. pair<int,int> cen[3];
  36. signed main()
  37. {
  38. 	read(T);
  39. 	while(T--)
  40. 	{
  41. 		read(n[0]);
  42. 		vector<vector<vector<int>>> a(3);
  43. 		rep(i,1,2)
  44. 		{
  45. 			n[i]=n[i-1];
  46. 			a[i].resize(n[i]+5);
  47. 			rep(j,1,n[i]-1)
  48. 			{
  49. 				int u,v; read(u,v);
  50. 				a[i][u].push_back(v);
  51. 				a[i][v].push_back(u);
  52. 			}
  53. 			vector<int> siz(n[i]+1);
  54. 			function<void(int,int)> dfs=[&](int u,int fa)
  55. 			{
  56. 				siz[u]=1;
  57. 				for(auto v:a[i][u]) if(v!=fa) dfs(v,u),siz[u]+=siz[v];
  58. 			}; dfs(1,0);
  59. 			int mn=1e18;
  60. 			cen[i]={0,0};
  61. 			function<void(int,int)> centroid=[&](int u,int fa)
  62. 			{
  63. 				int mx=n[i]-siz[u];
  64. 				for(auto v:a[i][u]) if(v!=fa) mx=max(mx,siz[v]);
  65. 				if(mx<mn) mn=mx,cen[i].first=u,cen[i].second=0;
  66. 				else if(mx==mn) cen[i].second=u;
  67. 				for(auto v:a[i][u]) if(v!=fa) centroid(v,u);
  68. 			}; centroid(1,0);
  69. 		}
  70. 		map<vector<int>,int> mp;
  71. 		int cur=0;
  72. 		function<int(int,int,int,int)> calc=[&](int id,int u,int fa,int spec)
  73. 		{
  74. 			vector<int> v={0};
  75. 			if(spec==u) v.push_back(-1);
  76. 			// cerr<<id<<" "<<u<<" "<<fa<<" "<<spec<<endl;
  77. 			for(auto vv:a[id][u]) if(vv!=fa) v.push_back(calc(id,vv,u,-1));
  78. 			sort(v.begin(),v.end());
  79. 			if(!mp.count(v)) mp[v]=++cur;
  80. 			return mp[v];
  81. 		};
  82. 		auto isomorphic=[&](int i,int j)->bool
  83. 		{
  84. 			// cerr<<"Checking isomorphism between tree "<<i<<" and tree "<<j<<endl;
  85. 			if((!!cen[i].second)!=(!!cen[j].second)) return 0;
  86. 			if(!cen[i].second) return calc(i,cen[i].first,0,-1)==calc(j,cen[j].first,0,-1);
  87. 			else
  88. 			{
  89. 				int rti=++n[i],rtj=++n[j];
  90. 				// cerr<<"New root "<<rti<<" for tree "<<i<<" and "<<rtj<<" for tree "<<j<<endl;
  91. 				auto orig_i=a[i],orig_j=a[j];
  92. 				a[i][cen[i].first].erase(remove(a[i][cen[i].first].begin(),a[i][cen[i].first].end(),cen[i].second),a[i][cen[i].first].end());
  93. 				a[i][cen[i].second].erase(remove(a[i][cen[i].second].begin(),a[i][cen[i].second].end(),cen[i].first),a[i][cen[i].second].end());
  94. 				a[j][cen[j].first].erase(remove(a[j][cen[j].first].begin(),a[j][cen[j].first].end(),cen[j].second),a[j][cen[j].first].end());
  95. 				a[j][cen[j].second].erase(remove(a[j][cen[j].second].begin(),a[j][cen[j].second].end(),cen[j].first),a[j][cen[j].second].end());
  96. 				a[i][rti].push_back(cen[i].first),a[i][cen[i].first].push_back(rti);
  97. 				a[i][rti].push_back(cen[i].second),a[i][cen[i].second].push_back(rti);
  98. 				a[j][rtj].push_back(cen[j].first),a[j][cen[j].first].push_back(rtj);
  99. 				a[j][rtj].push_back(cen[j].second),a[j][cen[j].second].push_back(rtj);
  100. 				// cerr<<"add success "<<rti<<" "<<rtj<<endl;
  101. 				int val=calc(i,rti,0,rti)==calc(j,rtj,0,rtj);
  102. 				a[i]=orig_i,a[j]=orig_j;
  103. 				--n[i],--n[j];
  104. 				return val;
  105. 			}
  106. 			return 0;
  107. 		};
  108. 		puts(isomorphic(1,2)?"YES":"NO");
  109. 	}
  110. 	return 0;
  111. }
Time limit exceeded #stdin #stdout 5s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/hJBjot
language:
C++14 (gcc 8.3)
created:
59 days 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!