fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll ;
  4. ll dp[500000+5];
  5. int b[500000+5];
  6. int a[500000+5];
  7. void DFS(int node,vector <int> G[],int used[],int parent[]){
  8.  
  9. used[node] = 1 ;
  10.  
  11. for(auto u: G[node]){ //iterating all children "u" of "node"
  12.  
  13. if(used[u]==0){
  14. //if this node/branch has never been visited before
  15. //just go into it and search it using dfs in recursion
  16. parent[u] = node ;
  17. DFS(u,G,used,parent);
  18.  
  19. }
  20. }
  21.  
  22.  
  23. //print(node)--->parent
  24. //----> bottom up traversal
  25. ll s = 0 ;
  26. for(auto child: G[node]){
  27.  
  28. if(child==parent[node]){
  29. //it means the child node is parent of the node
  30. //it is not the child
  31. //ignore it
  32. }
  33.  
  34. else{
  35. s = s + dp[child];
  36. }
  37. }
  38. dp[node] = s + 1;
  39.  
  40.  
  41. }
  42.  
  43. int main(){
  44. int n ;
  45. cin>>n ;
  46. vector <int> G[n+1];
  47. int i = 1 ;
  48. while(i<=n){
  49. cin>>a[i] ;
  50. i++;
  51. }
  52.  
  53. i = 1 ;
  54. while(i<=n){
  55. cin>>b[i] ;
  56. i++;
  57. }
  58.  
  59. i = 1 ;
  60. while(i<=n){
  61. int u,v;
  62. u = a[i],v = b[i];
  63. G[u].push_back(v);
  64. G[v].push_back(u);
  65. i++;
  66. }
  67. int used[n+1] = {0};
  68. int parent[n+1] = {0};
  69. DFS(0,G,used,parent); //starts from node 1
  70.  
  71. ll answer = 0;
  72. i = 1;
  73. while(i <= n){
  74. answer += (dp[i] + 4) / 5; // ceil division
  75. i++;
  76. }
  77.  
  78. cout<<(answer);
  79. return 0 ;
  80. }
  81.  
  82.  
Success #stdin #stdout 0s 7604KB
stdin
9 
1 1 1 9 9 9 9 7 8 
2 0 3 1 6 5 4 0 0 
stdout
10