Advertisement
jeff69

Untitled

Sep 11th, 2016
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.19 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int MX=2e5+5;
  4. typedef long long ll;
  5. typedef long double ld;
  6. bool color[MX];
  7.  
  8. vector<int> adj[MX];
  9. int n;
  10. void dfs(int x,int pa)
  11. {
  12.  
  13. for(int i=0;i<adj[x].size();i++)
  14. { int y=adj[x][i];
  15. if(y==pa)continue;
  16.  
  17.  
  18. color[x]=!color[x];
  19. cout<<x<<' ';
  20. dfs(y,x);
  21.  
  22.  
  23. }
  24. color[x]=!color[x];
  25. cout<<x<<' ';
  26. if(color[x])return;
  27. else
  28. {
  29. cout<<pa<<' '<<x<<' ';
  30. color[pa]=!color[pa];
  31. color[x]=!color[x];
  32. return;
  33. }
  34. }
  35. int main()
  36. {
  37. cin>>n;
  38. int t=0;
  39. for(int i=1;i<=n;i++)
  40. {
  41. int x;
  42. cin>>x;
  43. if(x==1)color[i]=1;
  44. else color[i]=0;
  45. t+=color[i];
  46. }
  47. for(int i=1;i<n;i++)
  48. {
  49. int x,y;
  50. cin>>x>>y;
  51. adj[x].push_back(y);
  52. adj[y].push_back(x);
  53. }
  54. if(t==n)
  55. {
  56. cout<<1;
  57. return 0;
  58. }
  59. for(int i=0;i<adj[1].size();i++)
  60. {
  61. cout<<1<<' ';
  62. if(i!=0)
  63. color[1]=!color[1];
  64. // cout<<"'"<<color[1]<<"'";
  65. dfs(adj[1][i],1);
  66.  
  67.  
  68. }
  69. if(color[1]==0)cout<<1;
  70. return 0;
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement