fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long int
  4. const int M = 1e9 + 7;
  5.  
  6. int dfs(int node,vector<int>adj[],vector<int>&dp,vector<int>&dis)
  7. {
  8.  
  9.     for(auto it:adj[node])
  10.     {
  11.         dis[node]+=dfs(it,adj,dp,dis);
  12.     }
  13.     for(auto it:adj[node])
  14.     {
  15.         dp[node]+=dp[it]+dis[it];
  16.     }
  17.     return dis[node];
  18. }
  19.  
  20. int main()
  21. {
  22.     ios_base::sync_with_stdio(false);
  23.     cin.tie(NULL);
  24.     int n;
  25.     cin >> n;
  26.     vector<int> adj[n+1];
  27.     vector<int> dp(n+1,0);
  28.     vector<int> dis(n+1,1);
  29.     for (int i = 0; i < n - 1; i++)
  30.     {
  31.         int u, v;
  32.         cin >> u >> v;
  33.         adj[u].push_back(v);
  34.     }
  35.     dfs(1,adj,dp,dis);
  36.  
  37.     for(int i=1;i<=n;i++) cout<<dp[i]<<" ";
  38.  
  39.     return 0;
  40. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
4
1 2
2 3
3 4
stdout
copy 
6 3 1 0
https://ideone.com/hzGh1E
language:
C++14 (gcc 8.3)
created:
4 days 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!