fork download
copy 
  1. #include<stdio.h>
  2. #include<algorithm>
  3. #include<random>
  4. using namespace std;
  5. random_device rd;
  6. mt19937_64 rng(rd());
  7.  
  8. #define M 100000
  9. #define N_ (N*2+1)
  10. #define N 100000
  11.  
  12. using u64=unsigned long long;
  13. int rt,n,m,hd[N],e[N_],Ln[N_],ii,diff,midedge,kil[N_],sz[N],o[N],p;
  14. u64 qwq[M+1],val[N],dis[N],sum;
  15.  
  16. void add(int u,int v){ ++ii; e[ii]=v;Ln[ii]=hd[u]; hd[u]=ii; }
  17. void dfs0(int u,int p){
  18. 	sz[u]=1;
  19. 	for(int j=hd[u];j;j=Ln[j])if(!kil[j]&&e[j]!=p){
  20. 		dfs0(e[j],u),sz[u]+=sz[e[j]];
  21. 	}
  22. }
  23. void dfs1(int u,int code){
  24. 	int x_=abs(sz[u]-(sz[rt]-sz[u]));
  25. 	if(x_<diff)diff=x_,midedge=code;
  26. 	for(int j=hd[u];j;j=Ln[j])if(!kil[j]&&(j^code^1))dfs1(e[j],j);
  27. }
  28.  
  29. void answer(int i,int j){
  30. 	printf("%d %d\n",i+1,j+1);
  31. 	exit(0);
  32. }
  33. void dfs2(int u,int code){
  34. 	dis[u]+=val[u];
  35. 	if(dis[u]==sum){
  36. 		answer(rt,u);
  37. 	}
  38. 	o[p++]=u;
  39. 	for(int j=hd[u];j;j=Ln[j])if(!kil[j]&&(j^code^1)) dis[e[j]]=dis[u],dfs2(e[j],j);
  40. }
  41.  
  42. void dfs3(int u,int code,u64 d){
  43. 	d+=val[u];
  44. 	int x=0;
  45. 	for(int j=(1<<20);j;j>>=1)
  46. 		if(j+x<p&&dis[o[x+j]]<=sum-d)x+=j;
  47. 	if(dis[o[x]]==sum-d)answer(o[x],u);
  48. 	for(int j=hd[u];j;j=Ln[j])if(!kil[j]&&(j^code^1)) dfs3(e[j],j,d);
  49. }
  50.  
  51. void DECOM(int u){
  52. 	dfs0(u,-1);
  53. 	diff=1900000;rt=u;dfs1(u,0);
  54.  
  55. 	if(midedge){
  56. 		int x=e[midedge],y=e[midedge^1];
  57. 		kil[midedge]=kil[midedge^1]=1;
  58. 		rt=x;dis[x]=p=0;dfs2(x,0);std::sort(o,o+p,[](int i,int j){return dis[i]<dis[j];});dfs3(y,0,0);
  59. 		rt=y;dis[y]=p=0;dfs2(y,0);std::sort(o,o+p,[](int i,int j){return dis[i]<dis[j];});dfs3(x,0,0);
  60.  
  61. 		DECOM(x),DECOM(y);
  62. 	}
  63. }
  64.  
  65. int main(){
  66. 	ii=1;
  67.  
  68. 	scanf("%d%d",&n,&m);
  69. 	for(int i=1;i<=m;++i)qwq[i]=rng(),sum+=qwq[i];
  70. 	for(int u,v,i=1;i<n;++i){
  71. 		scanf("%d%d",&u,&v),--u,--v;
  72. 		add(u,v),add(v,u);
  73. 	}
  74. 	for(int sz,w,i=0;i<n;++i){
  75. 		scanf("%d",&sz);
  76. 		while(sz--)scanf("%d",&w),val[i]+=qwq[w];
  77. 	}
  78.  
  79. 	DECOM(0);
  80. 	puts("No solution");
  81.  
  82. 	return 0;
  83. }
Success #stdin #stdout 0s 5340KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
No solution
https://ideone.com/3qlpeX
language:
C++14 (gcc 8.3)
created:
10 days 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!