Advertisement
Guest User

Untitled

a guest
Jan 28th, 2020
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.89 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int cnt;
  5. vector<int> moves;
  6.  
  7.  
  8. void dfs(vector<vector<int>> v, vector<int>& rec, vector<pair<int,int>> pares, int ini, bool changed, bool turn, bool both){
  9. rec[ini] = 1;
  10. for(int i = 0; i < v[ini].size(); i++){
  11. if(rec[v[ini][i]]==0){
  12. rec[v[ini][i]] = 1;
  13. if(!both){
  14. if(!changed){
  15. if(pares[v[ini][i]].first != pares[v[ini][i]].second){
  16. cnt++;
  17. moves.push_back(v[ini][i]);
  18. dfs(v,rec,pares,v[ini][i],true,false,false);
  19. }
  20. else{
  21. dfs(v,rec,pares,v[ini][i],false,false,false);
  22. }
  23. }
  24. else{
  25. if(!turn){
  26. if(pares[v[ini][i]].first != pares[v[ini][i]].second){
  27. cnt++;
  28. moves.push_back(v[ini][i]);
  29. dfs(v,rec,pares,v[ini][i],true,false,true);
  30. }
  31. else{
  32. dfs(v,rec,pares,v[ini][i],true,true,false);
  33. }
  34. }
  35. else{
  36. if(pares[v[ini][i]].first == pares[v[ini][i]].second){
  37. cnt++;
  38. moves.push_back(v[ini][i]);
  39. dfs(v,rec,pares,v[ini][i],false,false,false);
  40. }
  41. else{
  42. dfs(v,rec,pares,v[ini][i],true,false,false);
  43. }
  44. }
  45. }
  46. }
  47. else{
  48. if(pares[v[ini][i]].first == pares[v[ini][i]].second){
  49. cnt++;
  50. moves.push_back(v[ini][i]);
  51. dfs(v,rec,pares,v[ini][i],true,true,false);
  52. }
  53. else{
  54. dfs(v,rec,pares,v[ini][i],true,true,true);
  55. }
  56. }
  57. }
  58. }
  59. }
  60.  
  61. int main(){
  62. int n,x,y;
  63. cnt = 0;
  64. cin >> n;
  65. vector<vector<int>> v(n);
  66. vector<int> valores(n);
  67. vector<pair<int,int>> pares(n);
  68. for(int i = 0; i < n-1; i++){
  69. cin >> x >> y;
  70. x--;y--;
  71. v[y].push_back(x);
  72. }
  73. for(int i = 0; i < n; i++){
  74. cin >> x;
  75. pares[i].first = x;
  76. }
  77. for(int i = 0; i < n; i++){
  78. cin >> y;
  79. pares[i].second = y;
  80. }
  81. vector<int> rec(n,0);
  82. if(pares[0].first == pares[0].second){
  83. dfs(v,rec,pares,0,false,false,false);
  84. }
  85. else{
  86. cnt++;
  87. moves.push_back(0);
  88. dfs(v,rec,pares,0,true,false,false);
  89. }
  90. cout << cnt << '\n';
  91. for(auto i : moves){
  92. cout << i+1 << '\n';
  93. }
  94. return 0;
  95. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement