aka007

Codeforces#245A

May 12th, 2014
284
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.94 KB | None | 0 0
  1. /*******************
  2. Akash Agrawall
  3. IIIT HYDERABAD
  4. ***********************/
  5.  
  6.  
  7. #include<cstdio>
  8. #include<iostream>
  9. #include<cstdlib>
  10. #include<cmath>
  11. #include<cstring>
  12. #include<climits>
  13. #include<algorithm>
  14. #include<vector>
  15. #include<set>
  16. #include<map>
  17. #include<bitset>
  18. #include<stack>
  19. #include<queue>
  20. #include<stdio.h>
  21. #include<string.h>
  22. #include<math.h>
  23. #include<functional>
  24. #include<numeric>
  25. using namespace std;
  26. #define ll long long int
  27. #define FOR(i,a,b) for(i= (int )a ; i < (int )b ; ++i)
  28. #define rep(i,n) FOR(i,0,n)
  29. #define INF INT_MAX
  30. #define ALL(x) x.begin(),x.end()
  31. #define LET(x,a) __typeof(a) x(a)
  32. #define IFOR(i,a,b) for(LET(i,a);i!=(b);++i)
  33. #define EACH(it,v) IFOR(it,v.begin(),v.end())
  34. #define pb push_back
  35. #define sz(x) int(x.size())
  36. #define mp make_pair
  37. #define fill(x,v) memset(x,v,sizeof(x))
  38. #define max(a,b) ((a)>(b)?(a):(b))
  39. #define min(a,b) ((a)<(b)?(a):(b))
  40. #define pi(n) printf("%d ",n)
  41. #define pd(n) printf("%lf ",n)
  42. #define pdl(n) printf("%lf\n",n)
  43. #define pin(n) printf("%d\n",n)
  44. #define pl(n) printf("%lld",n)
  45. #define pln(n) printf("%lld\n",n)
  46. #define si(n) scanf("%d",&n)
  47. #define sl(n) scanf("%lld",&n)
  48. #define sd(n) scanf("%lf",&n)
  49. #define ss(n) scanf("%s",n)
  50. #define scan(v,n) vector<int> v;rep(i,n){ int j;si(j);v.pb(j);}
  51. #define mod (int)(1e9 + 7)
  52.  
  53. long long int gcd(long long int a,long long int b)
  54. {
  55. long long int c;
  56. while(a!=0)
  57. {
  58. c = a;
  59. a = b%a;
  60. b = c;
  61. }
  62. return b;
  63. }
  64.  
  65. vector<vector<int> > akash;
  66. int visited[300000];
  67. int init[300000];
  68. int goal[300000];
  69. int cnt=0;
  70. vector<int> answer;
  71. void definelevel(int value,int level,int even_times,int odd_times)
  72. {
  73. int len,i,times,valit,val,flag=0;
  74. visited[value]=1;
  75. len=akash[value].size();
  76. rep(i,len)
  77. {
  78. valit=akash[value][i];
  79. if(visited[valit]==0)
  80. {
  81. visited[valit]=1;
  82. if((level+1)&01)
  83. {
  84. flag=1;
  85. times=odd_times;
  86. }
  87. else
  88. times=even_times;
  89. val=(init[valit]+times)%2;
  90. init[valit]=val;
  91. if(init[valit]!=goal[valit])
  92. {
  93. answer.pb(valit);
  94. if(flag)
  95. definelevel(valit,level+1,even_times, odd_times+1);
  96. else
  97. definelevel(valit,level+1,even_times+1, odd_times);
  98. }
  99. else
  100. {
  101. definelevel(valit,level+1,even_times,odd_times);
  102. }
  103. }
  104. }
  105. }
  106. int main()
  107. {
  108. int n,u,v,initit,goalit,lev,i;
  109. si(n);
  110. FOR(i,1,1000000)
  111. akash.pb(vector<int>());
  112. rep(i,n-1)
  113. {
  114. si(u);si(v);
  115. akash[u].pb(v);
  116. akash[v].pb(u);
  117. }
  118. for(i=1;i<=n;i++)
  119. {
  120. si(initit);
  121. init[i]=initit;
  122. }
  123. for(i=1;i<=n;i++)
  124. {
  125. si(goalit);
  126. goal[i]=goalit;
  127. }
  128. if(init[1]!=goal[1])
  129. {
  130. answer.pb(1);
  131. definelevel(1,0,1,0);
  132. }
  133. else
  134. {
  135. definelevel(1,0,0,0);
  136. }
  137. lev=answer.size();
  138. pin(lev);
  139. rep(i,lev)
  140. pin(answer[i]);
  141.  
  142. /*garb=akash.size();
  143. printf("length of array:%d\n",garb);
  144. FOR(i,1,garb+1)
  145. {
  146. printf("%d->",i);
  147. garb1=akash[i].size();
  148. FOR(j,0,garb1)
  149. {
  150. printf("%d ",akash[i][j]);
  151. }
  152. printf("\n");
  153. }*/
  154. return 0;
  155. }
Advertisement
Add Comment
Please, Sign In to add comment