fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define MOD 1000000007
  3. #define quick ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  4. using namespace std;
  5. typedef long long ll;
  6. typedef long double ld;
  7.  
  8. vector<vector<ll> > graph;
  9. vector<int> initial,target;
  10. ll ans=0;
  11. vector<bool> visited;
  12.  
  13. void dfs(ll n,ll level,ll* mm)
  14. {
  15. 	ll *mark=new ll[2];
  16. 	mark[0]=mm[0];
  17. 	mark[1]=mm[1];
  18. 	//cout<<n<<" "<<level<<" "<<mark[0]<<" "<<mark[1]<<endl;
  19. 	visited[n]=true;
  20. 	if(initial[n]==target[n])
  21. 	{
  22. 		if(mark[level%2]==1)
  23. 		{
  24. 			mark[level%2]=0;
  25. 			ans++;
  26. 		}
  27. 	}
  28. 	else
  29. 	{
  30. 		initial[n]=target[n];
  31. 		if(mark[level%2]==0)
  32. 		{
  33. 			mark[level%2]=1;
  34. 			ans++;
  35. 		}
  36. 	}
  37. 	for(ll i=0;i<graph[n].size();i++)
  38. 	{
  39. 		if(!visited[graph[n][i]])
  40. 		{
  41. 			dfs(graph[n][i],level+1,mark);
  42. 		}
  43. 	}
  44. }
  45. int main()
  46. {
  47. 	ll n;
  48. 	cin>>n;
  49. 	graph.resize(n+1);
  50. 	initial.resize(n+1);
  51. 	target.resize(n+1);
  52. 	visited.resize(n+1);
  53. 	for(ll i=0;i<n-1;i++)
  54. 	{
  55. 		ll u,v;
  56. 		cin>>u>>v;
  57. 		graph[u].push_back(v);
  58. 		graph[v].push_back(u);
  59. 	}
  60. 	for(ll i=1;i<=n;i++)
  61. 		cin>>initial[i];
  62. 	for(ll i=1;i<=n;i++)
  63. 		cin>>target[i];
  64. 	ll *mark=new ll[2];
  65. 	mark[0]=mark[1]=0;
  66. 	dfs(1,1,mark);
  67. 	cout<<ans<<endl;
  68. 	return 0;
  69. }
  70.  
Success #stdin #stdout 0s 4412KB
comments (?)
stdin
copy 
3
1 2
2 3
1 0 1
0 1 0
stdout
copy 
2
https://ideone.com/JUAwnP
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!