fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. struct node{
  4. 	char c;
  5. 	int parent = -1;
  6. 	vector <int> edges;
  7. 	bool visited = false;
  8. };
  9. vector <node> tree;
  10. char target[] = "tareq&shawon";
  11. //char target[] = "taon";
  12. bool found = false;
  13. int firstIndex = -1;
  14. void dfs(int index, int curIndex){
  15. 	//printf("%c %d \n",tree[index].c, index+1);
  16. 	if(tree[index].visited || found)	return;
  17. 	tree[index].visited = true;
  18. 	if(target[curIndex] == tree[index].c){
  19. 		if(target[curIndex] == 'n'){	
  20. 			found = true;
  21. 			firstIndex = index;
  22. 			//printf("%d -> %c\n",index, tree[index].c);
  23. 		}
  24. 		curIndex++;
  25. 	}	
  26. 	for(int i=0;i<tree[index].edges.size();i++){
  27. 		int tmp = tree[index].edges[i];
  28. 		if(!tree[tmp].visited){	
  29. 			tree[tmp].parent = index;
  30. 			dfs(tmp, curIndex);
  31. 		}
  32. 		if(found)	return;
  33. 	}
  34. }
  35. int main() {
  36. 	// your code goes here
  37. 	int t,i,j,n,m,k,u,v,e[100009][2],cn = 0;
  38. 	char inp[10];
  39. 	scanf("%d",&t);
  40. 	while(t--){
  41. 		found = false;
  42. 		firstIndex = -1;
  43. 		cn++;
  44. 		tree.clear();
  45. 		scanf("%d",&n);
  46. 		for(i=0;i<n-1;i++){
  47. 			scanf("%d %d",&e[i][0],&e[i][1]);
  48. 		}
  49. 		for(i=0;i<n;i++){
  50. 			scanf("%s",inp);
  51. 			node n1;
  52. 			n1.c = inp[0];
  53. 			tree.push_back(n1);
  54. 		}
  55. 		for(i=0;i<n-1; i++){
  56. 			tree[e[i][0]-1].edges.push_back(e[i][1]-1);
  57. 			tree[e[i][1]-1].edges.push_back(e[i][0]-1);
  58. 		}
  59. 		for(i=0;i<n;i++){
  60. 			sort(tree[i].edges.begin(), tree[i].edges.end());
  61. 		}
  62. 	/*	for(i=0;i<n;i++){
  63. 			printf("%d %c --> ",i,tree[i].c);
  64. 			for(auto it : tree[i].edges){
  65. 				printf("%d ",it);
  66. 			}
  67. 			printf("\n");
  68. 		}*/
  69. 		dfs(0, 0);
  70. 		//printf("%d -> %c\n",firstIndex+1, tree[firstIndex].c);
  71. 		if(!found){
  72. 			printf("Case %d: NO\n",cn);
  73. 			continue;
  74. 		}
  75. 		int cur = firstIndex;
  76. 		while(1){
  77. 			bool s = false;
  78. 			for(int p=0; p<tree[cur].edges.size();p++){
  79. 				int tmp = tree[cur].edges[p];
  80. 				if(tree[tmp].visited)	continue;
  81. 				s = true;
  82. 				tree[tmp].visited = true;
  83. 				tree[tmp].parent = cur;
  84. 				cur = tmp;
  85. 				continue;
  86. 			}
  87. 			if(!s)	break;
  88. 		}
  89. 		//printf("%d -> %c\n",cur+1, tree[cur].c);
  90. 		stack <int> ans;
  91. 		while(tree[cur].parent != -1){
  92. 			ans.push(cur);
  93. 			cur = tree[cur].parent;
  94. 		}
  95. 		ans.push(cur);
  96. 		printf("Case %d: YES\n",cn);
  97. 		while(!ans.empty()){
  98. 			int tmp = ans.top();
  99. 			ans.pop();
  100. 			printf("%d ",tmp+1);
  101. 		}
  102. 		printf("\n");
  103. 	}
  104. 	return 0;
  105. }
  106.  
Success #stdin #stdout 0.01s 5380KB
comments (?)
stdin
copy 
2
16
1 7
1 10
7 14
7 12
12 2
2 16
16 11
16 5
14 4
4 9
10 3
3 8
8 6
8 13
5 15
p a a a o n q o o t n t n t n o
4
1 2
2 3
3 4
t a o x
stdout
copy 
Case 1: NO
Case 2: NO
https://ideone.com/Hghg1P
language:
C++ (gcc 8.3)
created:
2 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!