fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long int
  3. #define MOD 1000000007
  4. using namespace std;
  5. ll fast_pow(ll base,ll exp){if (exp == 0) return 1;if (exp == 1) return base % MOD;ll t = fast_pow(base, exp / 2);t = ((t% MOD) * (t%MOD)) % MOD;if (exp % 2 == 0)return t;else return ((base %  MOD) * t) % MOD;}
  6. class Graph
  7. {
  8.     //map<source, vector<destinations>>
  9.     map<ll,std::vector<ll>>adjList ;
  10.     public : 
  11.     Graph()
  12.     {
  13.  
  14.     }
  15.     void addEdge(ll source, ll destination, bool bidr = true)
  16.     {
  17.         adjList[source].push_back(destination);
  18.         if(bidr)
  19.             adjList[destination].push_back(source);
  20.     }
  21.     ll DFShelper(ll node, unordered_map<ll, bool> &visited, std::vector<ll> &dp)
  22.     {
  23.         if(dp[node] != -1) return dp[node];
  24.         visited[node] = true;
  25.         ll ans = 1;
  26.         for(auto &neighbour : adjList[node])
  27.         {
  28.             if(!visited[neighbour])
  29.             {
  30.                 ans *= ((1 + DFShelper(neighbour,visited,dp)) % MOD);
  31.                 ans = ans % MOD;
  32.             }
  33.         }
  34.         dp[node] = ans;
  35.         return dp[node];
  36.     }
  37.     void BFS(ll source, ll parent, std::vector<ll> &dp)
  38.     {
  39.         queue<ll> BFSqueue;
  40.         unordered_map<ll, bool> marked;
  41.         BFSqueue.push(source);
  42.         marked[source] = true;
  43.         while(!BFSqueue.empty())
  44.         {
  45.             ll node = BFSqueue.front();
  46.             BFSqueue.pop();
  47.             //push all unvisited neighbours of node in queue
  48.             for(auto &neighbour: adjList[node])
  49.             {
  50.                 if(!marked[neighbour])
  51.                 {
  52.                     parent = node;
  53.                     //dp[node]/(1+dp[neighbour]) removes answer of current node from parent subtree
  54.                     dp[neighbour] *= ((1 + dp[node]/(1+dp[neighbour]) % MOD) % MOD); //adding answer of parent 
  55.                     dp[neighbour] = dp[neighbour] % MOD;
  56.                     BFSqueue.push(neighbour);
  57.                     marked[neighbour] = true;
  58.                 }
  59.             }
  60.         }
  61.     }
  62. };
  63. int main()
  64. {
  65.     ios_base::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);
  66.     ll n;
  67.     cin >> n;
  68.     Graph g;
  69.     for(ll i = 1; i < n; i++)
  70.     {
  71.         ll a;
  72.         cin >> a;
  73.         g.addEdge(i,a-1);
  74.     }
  75.     vector<ll> dp(n,-1);
  76.     unordered_map<ll, bool> visited;
  77.     g.DFShelper(0, visited,dp);
  78.     g.BFS(0,-1,dp);
  79.     for (auto &i : dp) cout << i << " ";
  80.     return 0;
  81. }
Success #stdin #stdout 0s 4408KB
comments (?)
stdin
copy 
5
1 2 3 4
stdout
copy 
5 8 9 8 5
https://ideone.com/XVoLRa
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

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!